Preconditioners for Indefinite Linear Systems Arising in Surface Parameterization

Proceedings, 10th International Meshing Roundtable, Sandia National Laboratories, pp.71-81, October 7-10 2001

MESHING
RESEARCH
CORNER

10th International Meshing Roundtable
Newport Beach, California, U.S.A.
October 7-10, 2001

University of Illinois at Urbana-Champaign, Urbana, lI/inois 61801, USA. Email: { liesen | sturler | sheffa | aydin | siefert }@uiuc.edu

Abstract
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 efficient 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.

Download Full Paper (Postscript Format)