Preconditioners for Indefinite Linear Systems Arising in Surface Parameterization.
Jörg Liesen, Eric de Sturler, Alla Sheffer, Yelda Aydin, Chris Siefert · 2001
In [19] we introduced a new algorithm for computing planar triangulations of faceted surfaces for surface parameterization. Our algorithm computes a mapping that minimizes the distortion of the surface metric structures (lengths, angles, etc.). Compared with alternative approaches, the algorithm provides a significant improvement in robustness and applicability; it can handle more complicated surfaces and it does not require a convex or predefined planar domain boundary. However, our algorithm involves the solution of a constrained minimization problem. The potential high cost in solving the optimization problem has given rise to concerns about the applicability of the method, especially for very large problems. This paper is concerned with the ecient solution of the symmetric indefinite linear systems that arise when Newton's method is applied to the constrained minimization problem. In small to moderate size models the linear systems can be solved efficiently with a sparse direct method. We give examples from computations with the SuperLU package [6]. For larger models we have to use preconditioned iterative methods. We develop a new preconditioner that takes into account the structure of our linear systems. Some preliminary experimental results are shown that indicate the effectiveness of this approach.