曲阜师范大学学报(自然科学版)
麯阜師範大學學報(自然科學版)
곡부사범대학학보(자연과학판)
JOURNAL OF QUFU NORMAL UNIVERSITY(NATURAL SCIENCE)
2003年
2期
4-12
,共9页
空间树形算法%力场评估%N-体仿真%PRAM%cost最优算法
空間樹形算法%力場評估%N-體倣真%PRAM%cost最優算法
공간수형산법%력장평고%N-체방진%PRAM%cost최우산법
考虑两种情况:在3维空间中给出n个质点,计算每一粒子施加在其它粒子上的力,成对的相互作用可能有万有引力或者Lennard-Jones. 上述两种情况的力,当两粒子间的距离达到无限大时消失. 既然n个质点,两两相互作用共有[n(n-1)]/2对,直接算法对力的估算所需时间为O(n\+2). 这对天文中的仿真所用时间是非常大的. 该文提出了一种O(log n)算法,使用n/log n处理器CREW PRAM来计算n体仿真中的场. 这种最优并行算法的关键是利用一个相同的非递归自上而下的过程来代替一个递归的自上而下的计算过程. 这种相似的算法对力场计算也产生了一个新的O(n)时间序列算法.
攷慮兩種情況:在3維空間中給齣n箇質點,計算每一粒子施加在其它粒子上的力,成對的相互作用可能有萬有引力或者Lennard-Jones. 上述兩種情況的力,噹兩粒子間的距離達到無限大時消失. 既然n箇質點,兩兩相互作用共有[n(n-1)]/2對,直接算法對力的估算所需時間為O(n\+2). 這對天文中的倣真所用時間是非常大的. 該文提齣瞭一種O(log n)算法,使用n/log n處理器CREW PRAM來計算n體倣真中的場. 這種最優併行算法的關鍵是利用一箇相同的非遞歸自上而下的過程來代替一箇遞歸的自上而下的計算過程. 這種相似的算法對力場計算也產生瞭一箇新的O(n)時間序列算法.
고필량충정황:재3유공간중급출n개질점,계산매일입자시가재기타입자상적력,성대적상호작용가능유만유인력혹자Lennard-Jones. 상술량충정황적력,당량입자간적거리체도무한대시소실. 기연n개질점,량량상호작용공유[n(n-1)]/2대,직접산법대력적고산소수시간위O(n\+2). 저대천문중적방진소용시간시비상대적. 해문제출료일충O(log n)산법,사용n/log n처리기CREW PRAM래계산n체방진중적장. 저충최우병행산법적관건시이용일개상동적비체귀자상이하적과정래대체일개체귀적자상이하적계산과정. 저충상사적산법대력장계산야산생료일개신적O(n)시간서렬산법.
