格點演算法

⑴ 　Delaunay剖分的Bowyer演算法

在實際計算中Delaunay剖分通常採用如下定義：在形成的每個三角形的外接圓內都不包含網格點。

據此，Lawson和Bowyer提出的Delaunay三角形化演算法，是通過不斷地增加網格點迭代計算的。演算法分為如下幾點：

（1）判斷新加入的格點與三角形外接圓的內外關系，如果在某三角形外接圓內，則這個三角形需要改造。

（2）將所有需要改造的三角形集中起來，把它們的相鄰邊去掉，構成一個凸的多邊形。

（3）找到這個多邊形的外邊界，並利用它們的相鄰關系把它們連接起來構成一個頭尾相接的環。

（4）將環上的每兩個相鄰的網格點取出，與待加入的網格點構造三角形，計算其外心，並將相鄰三角形的信息建立起來，將三角形網格點和相鄰三角形信息儲貯在只包含這些三角形的Delaunay剖分的數據結構數組中。

（5）將上述新加入的三角形數據結構數組替換三角形數據結構數組中需要改造的三角形，並對三角形重新編號，從而得到新的結構數組。

⑵ 數論包括哪些內容

包括：初等數論、解析數論、代數數論、幾何數論、計算數論、超越數論、組合數論、算術代數幾何。

1、初等數論

初等數論主要就是研究整數環的整除理論及同餘理論。此外它也包括了連分數理論和少許不定方程的問題。本質上說，初等數論的研究手段局限在整除性質上。

初等數論中經典的結論包括算術基本定理、歐幾里得的質數無限證明、中國剩餘定理、歐拉定理（其特例是費馬小定理）、高斯的二次互反律， 勾股方程的商高定理、佩爾方程的連分數求解法等等。

2、解析數論

藉助微積分及復分析（即復變函數）來研究關於整數的問題，主要又可以分為乘性數論與加性數論兩類。乘性數論藉由研究積性生成函數的性質來探討素數分布的問題，其中質數定理與狄利克雷定理為這個領域中最著名的古典成果。加性數論則是研究整數的加法分解之可能性與表示的問題，華林問題是該領域最著名的課題。

解析數論的創立當歸功於黎曼。他發現了黎曼zeta函數之解析性質與數論中的素數分布問題存在深刻聯系。確切的說， 黎曼ζ函數的非平凡零點的分布情況決定了素數的很多性質。黎曼猜測， 那些零點都落在復平面上實部為1/2的直線上。這就是著名的黎曼假設—千禧年大獎難題之一。值得注意的是， 歐拉實際上在處理素數無限問題時也用到了解析方法。

解析數論方法除了圓法、篩法等等之外， 也包括和橢圓曲線相關的模形式理論等等。此後又發展到自守形式理論，從而和表示論聯系起來。

3、代數數論

代數數論，將整數環的數論性質研究擴展到了更一般的整環上，特別是代數數域。一個主要課題就是關於代數整數的研究，目標是為了更一般地解決不定方程求解的問題。其中一個主要的歷史動力來自於尋找費馬大定理的證明。

代數數論更傾向於從代數結構角度去研究各類整環的性質， 比如在給定整環上是否存在算術基本定理等等。

這個領域與代數幾何之間的關聯尤其緊密， 它實際上也構成了交換代數理論的一部分。它也包括了其他深刻內容，比如表示論、p-adic理論等等。

4、幾何數論

主要在於通過幾何觀點研究整數（在此即格點， 也稱整點）的分布情形。最著名的定理為Minkowski定理。這門理論也是有閔科夫斯基所創。對於研究二次型理論有著重要作用。

5、計算數論

藉助電腦的演算法幫助研究數論的問題，例如素數測試和因數分解等和密碼學息息相關的課題。

⑶ NUFFT的計算難點在哪裡

前難點. NUFFT 的計算比 FFT慢。NUFFT包括兩個步驟：卷積插值 （gridding）和FFT，其計算復雜度由卷積插值步驟決定。最近幾年對卷積插值快速計算的研究，有包括優化卷積窗函數（在保證插值精度的前提下縮小窗寬，降低過采樣比等），有基於openmp加速的NFFT庫和基於GPU加速的gpuNUFFT庫等。所以計算慢已經不是NUFFT的突出問題。現難點. NUFFT計算結果的理解，可逆性，和逆變換的計算問題。先看FFT變換：在滿足奈奎斯特采樣定理條件下，其對一個帶寬有限的一維連續信號做等間隔采樣得到長度為N的離散信號x[n]，其離散傅里葉變換記作矩陣向量相乘的形式為：f = F*x, 其中F為大小為N x N 的傅里葉變換矩陣，f[k] 是該信號的離散頻譜，在K個等間隔頻率點上，一般K = N。該變換有FFT演算法可以快速計算（FFT的優點1）。從這個頻譜再經過inverse FFT變換：x = F^(-1) * f仍能夠得到原信號（FFT的優點2），F^(-1)表示F的逆。在數學上，F矩陣是可逆的，並且F矩陣的共軛轉置等於F矩陣的逆，也即F^(-1) = F^(H) ，而F^(H) 同樣可以用FFT演算法快速計算（FFT的優點3）. 所以FFT變換是可逆的，並且正逆變換都有快速計算演算法。但是對同一個連續信號做非等間隔采樣（變密度采樣）得到長度仍為N的離散信號t[n]，做NUFFT變換並假設得到的結果頻譜y的頻率點是等間隔的，其矩陣向量乘的形式為：y = E * t那麼這個頻譜 y 和 f 是不等價的（問題1）。從這個頻譜 y 經過逆變換 （t1 = E^(-1) * y）得到的 t1等不等於t，以及這個逆變換E^(-1) 與 E^(H) (E矩陣的共軛轉置)之間的關系是什麼都成了問題。