Abstract
We consider the problem of finding the symmetric positive definite preconditionerM of a given form- e.g., having nonzero elements only in specified positions — which minimizes the ratio of the largest to smallest eigenvalue ofM −1 A, for a given symmetric positive definitive matrixA. We show how this problem can be expressed as one of minimizing a convex function and how an optimization code can be used to solve the problem numerically. Results are presented showing optimal preconditioners of various sparsity patterns and comparing these to preconditioners that have been proposed in the literature. Several conjectures are made, based on results from the optimization code.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
O. Axelsson and P. S. Vassilevski,Algebraic multilevel preconditioning methods, I, to appear inNum. Math.
M. W. Benson and P. O. Frederickson,Iterative solution of large sparse linear systems arising in certain multidimensional approximation problems, Utilitas Math. 22, 127–140, 1982.
M. Benson, J. Krettma, and M. Wright,Parallel algorithms for the solution of certain large sparse linear systems, Int. J. Comp. Math. 16, 245–260, 1984.
P. E. Bjørstad and O. B. Widlund,Iterative methods for the solution of elliptic problems on regions partitioned into substructures, SIAM Jour. Num. An. 23, #6, 1097–1120, Dec., 1986.
A. Brandt,Multilevel adaptive solutions to boundary value problems, Math of Comp. 31 333–390, 1977.
T. F. Chan,Analysis of preconditioners for domain decomposition, SIAM Jour. Num. An. 24, #2, 382–390, Apr., 1987.
T. Chan, private communication.
P. Concus and G. Golub,Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations, SIAM J. Numer. Anal. 10, #6, 1103–1120, December, 1973.
J. Cosgrove, J. Diaz, and A. Griewank,Approximate inverse preconditionings for sparse linear systems, to appear.
G. Csordas and R. S. Varga,Comparisons of regular splittings of matrices, Num. Math. 44, 23–35, 1984.
S. Demko, W. F. Moss, and P. W. Smith,Decay rates for inverses of band matrices, Math. of Comp. 43, 491–499, 1984.
J. Demmel,The condition number of equivalence transformations that block diagonalize matrix pencils, SIAM J. Numer. Anal, 20, #3, 599–610, June, 1983.
P. F. Dubois, A. Greenbaum and G. H. Rodrigue,Approximating the inverse of a matrix for use in iterative algorithms on vector processors, Computing 22, 257–268, 1979.
S. Eisenstat, J. Lewis, and M. Schultz,Optimal block diagonal scaling of block 2-cyclic matrices, Lin. Alg. Appl., 44, 181–186, 1982.
L. Elsner,A note on optimal block-scaling of matrices, Num. Math. 44, 127–128, 1984.
R. Fletcher,A survey of algorithms for unconstrained optimization, Rep. TP456, Theoretical Physics Division, A.E.R.E. Harwell, Didcot, Berks, England, 1971.
G. E. Forsythe and E. G. Strauss,On best conditioned matrices, Proc. Amer. Math. Soc. 6, 340–345, 1955.
A. Greenbaum,Comparison of splitting used with the conjugate gradient algorithm, Num. Math. 33, 181–194, 1979.
A. Greenbaum,Behavior of slightly perturbed Lanczos and conjugate gradient recurrences, Lin. Alg. Appl. 113, 7–63, 1989.
A. Greenbaum,Diagonal scalings of the Laplacian as preconditioners for other elliptic operators, to appear.
I. Gustafsson,A class of 1st order factorization methods, BIT 18, 142–156, 1978.
O. G. Johnson, C. A. Micchelli, and G. Paul,Polynomial preconditioning for conjugate gradient calculations, SIAM Jour. Num. An. 20, #2, 362–376, 1983.
L. Kolotilina and A. Yeremin,On a family of two-level preconditionings of the incomplete block factorization type, Soviet J. of Num. An. and Math. Modelling 1, 293–320, 1986.
O. H. Liong,Fast approximate solution of large scale sparse linear systems, J. Comp. Appl. Math. 10, 45–54, 1984.
T. A. Manteuffel and S. V. Parter,Preconditioning and boundary conditions, LA-UR-88-2626, Los Alamos Technical Report, July, 1988.
A. Mayo,The fast solution of Poisson's and the biharmonic equations on irregular regions, SIAM Jour. Num. An. 21, #2, 285–299, Apr., 1984.
J. A. Meijerink and H. A. van der Vorst,An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. Comp. 31, 148–162, 1977.
M. L. Overton,On minimizing the maximum eigenvalue of a symmetric matrix, SIAM J. Mat. An. Appl., Vol. 9, #2, 256–268, Apr., 1988.
C. Romine, private communication.
A. van der Sluis,Condition numbers and equilibration matrices, Num. Math. 14, 14–23, 1969.
R. S. Varga,Matrix iterative analysis, Prentice-Hall, Englewood Cliffs, N.J., 1962.
O. Widlund, private communication.
D. M. Young,Iterative solution of large linear systems, Academic Press, New York, 1971.
Author information
Authors and Affiliations
Additional information
This work was supported by the Advanced Research Projects Agency of the Department of Defense under contract F49620-87-C-0065 and by the Applied Mathematical Sciences Program of the U.S. Department of Energy under contract DE-AC02-76ER03077.
Rights and permissions
About this article
Cite this article
Greenbaum, A., Rodrigue, G.H. Optimal preconditioners of a given sparsity pattern. BIT 29, 610–634 (1989). https://doi.org/10.1007/BF01932737
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01932737