Summary
We study symmetric positive definite linear systems, with a 2-by-2 block matrix preconditioned by inverting directly one of the diagonal blocks and suitably preconditioning the other. Using an approximate version of Young's “Property A”, we show that the condition number of the Schur complement is smaller than the condition number obtained by the block-diagonal preconditioning. We also get bounds on both condition numbers from a strengthened Cauchy inequality. For systems arising from the finite element method, the bounds do not depend on the number of elements and can be obtained from element-by-element computations. The results are applied to thep-version finite element method, where the first block of variables consists of degrees of freedom of a low order.
Similar content being viewed by others
References
Adams, L.M., Jordan, H.F.: Is SOR color-blind?. SIAM J. Sci. Stat. Comput.7, 490–506 (1986)
Axelsson, O., Gustafsson, I.: Preconditioning and two-level multigrid methods of arbitrary degree of approximation. Math. Comput.40, 219–242 (1983)
Babuška, I., Craig, A.W., Mandel, J., Pitkäranta, J.: Efficient preconditioning for thep-version finite element in two dimensions. SIAM J. Numer. Anal. (to appear)
Babuška, I., Suri, M.: Thep- andh-p versions of the finite element method. International Conference on Spectral and High Order Methods for partial Differential Equations, Como, Italy, June 1989. Comput. Methods Appl. Mech. Eng. (submitted)
Bank, R.E., Dupont, T.F.: Analysis of a Two-Level Scheme for Solving Finite Element Equations. Tech. Rep. CNA-159, Center for Numerical Analysis, University of Texas at Austin, 1980
Braess, D.: The contraction number of a multigrid method for solving the Poisson equation. Numer. Math.37, 387–404 (1981)
Bramble, J.H., Pasciak, J.E., Schatz, A.H.: The construction of preconditioners for elliptic problems by substructuring. I. Math. Comput.47, 103–134 (1986)
Concus, P., Golub, G.H., O'Leary, D.P.: A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations. In: Buch, J.R., Rose, D.J. (eds.) Sparse Matrix Computations, pp. 309–332. New York: Academic Press 1976
Craig, A.W., Zienkiewicz, O.C.: A multigrid algorithm using a hierarchical finite element basis. In: Paddon, D.J., Holstein, H. (eds.) Multigrid Methods for Integral and Differential Equations. Oxford: Clarendon Press 1985
Golub, G.H., Van Loan, C.F.: Matrix Computation. John Hopkins University Press, second ed., 1989
Hackbusch, W.: Multigrid Methods—Theory and Applications. Berlin: Springer 1986
Mandel, J.: Hierarchical preconditioning and partial orthogonalization for thep-version finite element method. In: Proceedings of the Third International Symposium on Domain Decomposition Methods for Partial Differential Equations, Houston, March 1989, edited by T.F. Chan, R. Glowinski, O. Widlund, SIAM, Philadelphia, 1990
Mandel, J.: Iterative solvers by substructuring for thep-version finite element method. International Conference on Spectral and High Order Methods for Partial Differential Equations, Como, Italy, June 1989; Comput. Methods. Appl. Mech. Eng. (to appear)
Milaszewicz, J.P.: Improving Jacobi and Gauss-Seidel iterations. Linear Algebra Appl.93, 161–170 (1987)
Reid, J.K.: The use of conjugate gradients for systems of linear equations possessing “Property A”. SIAM J. Numer. Anal.9, 325–332 (1972)
Szabó, B.A.: PROBE Theoretical Manual. Noetic Technologies, St. Louis, MO, 1985
Varga, R.S.: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1962
von Neumann, J., Goldstine, H.H.: Numerical inverting of matrices of high order. Bull. Am. Math. Soc.53, 1021–1099 (1947)
Young, D.M.: Generalizations of Property A and consistent orderings. SIAM J. Numer. Anal.9, 454–463 (1972)
Young, D.M.: Iterative Solution of Large Linear Systems. New York: Academic Press 1971
Yserentant, H.: On the multilevel splitting of finite element spaces. Numer. Math.49, 379–412 (1986)
Zienkiewicz, O.C.: The Finite Element Method, third Ed. London: McGraw Hill 1977
Note added in proof
Keyes, D.E., Gropp, W.E.: A comparison of domain decomposition techniques for elliptic partial differential equations and their parallel implementation. SIAM Review8, 167s-202s (1987)
Vassilevski, P.S.: Nearly optimal iterative methods for solving finite element equations based on the multilevel splitting of the matrix, Report 1989-09, Institute for Scientific Computation, University of Wyoming, Laramie, Wyoming, 1989
Author information
Authors and Affiliations
Additional information
The research reported here was supported by the National Science Foundation under grant DMS-8704169.