表面參數化中的大型矩陣計算問題

Abstract

這個計畫研究表面參數化中所遇到的一些矩陣計算的問題，主要是大型稀疏的線性系統求解以及用牛頓法求根的問題。我們將表面參數化的問題分為兩大類，第一類是找出適當的映射關係，包含調和映射跟保角映射。第二類是計算調和 1-形式以及全純 1-形式的基底。 調和映射將具有單連通以及獨一邊界的三維空間網格對應到平面的單位圓。調和映射經由解一個優化問題得到，而該優化問題又等價於解一個線性系統。在適當的選取權重情況下，線性系統的矩陣可證明為對稱正定甚至是 M 矩陣，我們考慮用預條件共軛梯度法來解這樣的線性系統。我們希望利用模型化簡的手法能夠很快地估算到適當的預條件矩陣。至於保角映射這裡考慮的是將虧格數零的封閉網格保角映射到球面上，這樣的保角映射可透過解非線性熱擴散方程來得到。由於用顯式尤拉法來解這樣的方程常會有不收斂的狀況，我們希望設計出比顯式尤拉法更有效率的數值方法。 第二類的演算法首先處理虧格數大於零的封閉網格以得到調和1-形式群的基底。首先需計算上同調群的基底，接著解一個離散帕森方程來得到調和1-形式群的基底。離散帕森方程可表示成一個線性系統，因此我們又遇到跟計算調和映射相類似的計算問題，我們希望在調和映射那邊發展的方法可以應用到找調和1-形式群的基底。至於找全純 1-形式群基底所面臨的挑戰也是在於是否有良好解相關線性系統的方法。

In this project, we aim to develop some fast numerical algorithms for surface parameterization. We will focus on four algorithms that compute harmonic mappings, spherical conformal mappings, harmonic one-forms and holomorphic one-forms, respectively. A harmonic mapping maps a simply connected mesh with a single boundary to the unit disk. A numerical challenge of this algorithm is to solve an energy optimization problem which is equivalent to solving a linear system. There are numerous formulations of optimization problems and consequently induce different linear systems. We focus on the linear systems with coefficient matrices being M-matrices or symmetric positive definite ones. Due to the symmetric positive definiteness we solve these linear systems by the preconditioned conjugate gradient (PCG) method with the Symmetric Successive Over-Relaxation (SSOR) preconditioner. The SSOR preconditioner is parameterized. Choosing an optimal value of the parameter will lead to faster convergence. However calculating an optimal one may be too expensive. Inspired by the concept of model reduction, we devise efficient strategies for calculating a near optimal value and make the PCG a viable method. Theoretic analysis is to be considered. The Riemann mapping algorithm computes a conformal mapping from a genus zero mesh with a single boundary to the unit disk. The numerical challenge of the Riemann mapping algorithm is to calculate a spherical conformal mapping, an intermediate step of the Riemann mapping algorithm. Similar to the case of planar parameterizations by harmonic maps, solving systems of equations is a necessity. It becomes more challenging since we are facing nonlinear systems of equations instead of linear systems. To conquer this question, we devise a novel quasi-implicit Euler method. Numerical experiments reveal that the quasi-implicit Euler method is much superior to the explicit Euler method. Stability analysis of the quasi-implicit Euler method is in pursuit. Next, we turn to the computation of harmonic one-form basis. The algorithm inputs a closed nonzero genus mesh and outputs a set of basis of harmonic one-form group. After calculating a set of basis of cohomology group, it is time to set a linear system and the similar challenge to the case of harmonic mappings appears. We hope that the PCG strategy for solving the linear systems associated with harmonic mappings also applies in this case. Finally the computation of the basis of the holomorphic one-form group is to compute the basis of harmonic one-forms and their conjugate harmonic one-forms and pair each harmonic one-form with its conjugate. Consequently the bottleneck is also the lack of an efficient and robust linear solver.