HR: 0800h
AN: DI21A-0338    [Abstracts]
TI: Guaranteed Convergence Rates for Iterative Solutions of Elliptic PDEs with Strongly Varying Coefficients
AU: * Elgersma, M R
EM: michael_elgersma@juno.com
AF: Honeywell, 3660 Technology Drive, Minneapolis, MN 55418, United States
AU: Yuen, D A
EM: daveyuen@gmail.com
AF: University of Minnesota, Department of Geology and Geophysics and University of Minnesota Supercomputing Institute, Minneapolis, MN 55455, United States
AB: The convergence rate of iterative solvers is determined by the condition number of the matrix associated with the linearized system of equations. The number of iterations required by Krylov solvers or by Jacobi iteration for the coarsest grid in multigrid methods, both depend on the condition number. A matrix representing an elliptic PDE on a discretized region can be considered as a graph with the diagonal matrix elements representing the vertices, and the off-diagonal matrix elements representing the edges of the graph. Spectral graph theory gives upper and lower bounds for the condition number of any graph in terms of the vertex degree and edge weights. Given the largest ball that fits inside the computational domain, the condition number of a matrix is directly related to the ratio of the sum of the vertex degrees inside the ball, and the sum of the edge weights at the boundary of the ball. This knowledge can be used to construct a grid that has the lowest possible condition number. The lowest condition number and lowest number of cells is obtained by gridding or triangulating the region as coarsely as possible while still preserving the topology of boundaries and surfaces of discontinuity. This is achieved by using small cells near boundaries and larger cells further from boundaries. The resulting iteration number bounds are verified using a system of two coupled Laplacians to solve a mantle convection problem with dozens of sinking spheres whose velocity is several orders of magnitude greater than the surrounding mantle.
DE: 0560 Numerical solutions (4255)
DE: 3225 Numerical approximations and analysis (4260)
DE: 3255 Spectral analysis (3205, 3280)
DE: 5724 Interiors (8147)
DE: 5749 Origin and evolution
SC: Study of the Earth's Deep Interior [DI]
MN: 2007 Fall Meeting