article

On block diagonal and Schur complement preconditioning

Author:

Jan MandelAuthors Info & Claims

Numerische Mathematik, Volume 58, Issue 1

Pages 79 - 93

https://doi.org/10.1007/BF01385611

Published: 01 December 1990 Publication History

Abstract

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.

References

[1]

Adams, L.M., Jordan, H.F.: Is SOR color-blind?. SIAM J. Sci. Stat. Comput.7, 490---506 (1986)

Digital Library

[2]

Axelsson, O., Gustafsson, I.: Preconditioning and two-level multigrid methods of arbitrary degree of approximation. Math. Comput.40, 219---242 (1983)

[3]

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)

[4]

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)

[5]

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

[6]

Braess, D.: The contraction number of a multigrid method for solving the Poisson equation. Numer. Math.37, 387---404 (1981)

Digital Library

[7]

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)

Digital Library

[8]

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

[9]

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

[10]

Golub, G.H., Van Loan, C.F.: Matrix Computation. John Hopkins University Press, second ed., 1989

[11]

Hackbusch, W.: Multigrid Methods--Theory and Applications. Berlin: Springer 1986

[12]

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

[13]

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)

[14]

Milaszewicz, J.P.: Improving Jacobi and Gauss-Seidel iterations. Linear Algebra Appl.93, 161---170 (1987)

[15]

Reid, J.K.: The use of conjugate gradients for systems of linear equations possessing "Property A". SIAM J. Numer. Anal.9, 325---332 (1972)

[16]

Szabó, B.A.: PROBE Theoretical Manual. Noetic Technologies, St. Louis, MO, 1985

[17]

Varga, R.S.: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1962

[18]

von Neumann, J., Goldstine, H.H.: Numerical inverting of matrices of high order. Bull. Am. Math. Soc.53, 1021---1099 (1947)

[19]

Young, D.M.: Generalizations of Property A and consistent orderings. SIAM J. Numer. Anal.9, 454---463 (1972)

[20]

Young, D.M.: Iterative Solution of Large Linear Systems. New York: Academic Press 1971

[21]

Yserentant, H.: On the multilevel splitting of finite element spaces. Numer. Math.49, 379---412 (1986)

Digital Library

[22]

Zienkiewicz, O.C.: The Finite Element Method, third Ed. London: McGraw Hill 1977

Cited By

Anciaux-Sedrakian AGrigori LJorti ZPapež JYousef S(2020)Adaptive solution of linear systems of equations based on a posteriori error estimatorsNumerical Algorithms10.1007/s11075-019-00757-z84:1(331-364)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1007/s11075-019-00757-z
Huang NMa C(2019)Spectral analysis of the preconditioned system for the 3 × 3 block saddle point problemNumerical Algorithms10.1007/s11075-018-0555-681:2(421-444)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s11075-018-0555-6
Carraro TFriedmann EGerecht D(2016)Coupling vs decoupling approaches for PDE/ODE systems modeling intercellular signalingJournal of Computational Physics10.1016/j.jcp.2016.03.020314:C(522-537)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.jcp.2016.03.020
Show More Cited By

On block diagonal and Schur complement preconditioning
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
    2. Numerical analysis

Recommendations

Constraint Schur complement preconditioners for nonsymmetric saddle point problems

We consider constraint preconditioners for block two-by-two generalized saddle point problems, this is the general nonsymmetric, nonsingular case where the (1,2) block need not equal the transposed (2,1) block and the (2,2) block may not be zero. The ...
Block triangular Schur complement preconditioners for saddle point problems and application to the Oseen equations

We study block triangular Schur complement preconditioners for two by two block linear systems. Two block triangular Schur complement preconditioners are derived from a splitting of the (1,1)-block of the two by two block matrix. The two block ...
Block Diagonal and Schur Complement Preconditioners for Block-Toeplitz Systems with Small Size Blocks

In this paper we consider the solution of Hermitian positive definite block-Toeplitz systems with small size blocks. We propose and study block diagonal and Schur complement preconditioners for such block-Toeplitz matrices. We show that for some block-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Numerische Mathematik

Numerische Mathematik Volume 58, Issue 1

December 1990

873 pages

ISSN:0029-599X

Issue’s Table of Contents

Copyright © Copyright © 1990 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 December 1990

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Anciaux-Sedrakian AGrigori LJorti ZPapež JYousef S(2020)Adaptive solution of linear systems of equations based on a posteriori error estimatorsNumerical Algorithms10.1007/s11075-019-00757-z84:1(331-364)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1007/s11075-019-00757-z
Huang NMa C(2019)Spectral analysis of the preconditioned system for the 3 × 3 block saddle point problemNumerical Algorithms10.1007/s11075-018-0555-681:2(421-444)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s11075-018-0555-6
Carraro TFriedmann EGerecht D(2016)Coupling vs decoupling approaches for PDE/ODE systems modeling intercellular signalingJournal of Computational Physics10.1016/j.jcp.2016.03.020314:C(522-537)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.jcp.2016.03.020
Vicente da Silva MCastro LPereira E(2015)On the parallel implementation of a hybrid-mixed stress formulationComputers and Structures10.1016/j.compstruc.2015.05.022158:C(71-81)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.compstruc.2015.05.022
Witkowski TLing SPraetorius SVoigt A(2015)Software concepts and numerical algorithms for a scalable adaptive parallel finite element methodAdvances in Computational Mathematics10.1007/s10444-015-9405-441:6(1145-1177)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s10444-015-9405-4
Lee ISaad A(2013)Towards a recursive iterative preconditionerProceedings of the 51st annual ACM Southeast Conference10.1145/2498328.2500054(1-2)Online publication date: 4-Apr-2013
https://dl.acm.org/doi/10.1145/2498328.2500054
Agarwal SSnavely NSeitz SSzeliski R(2010)Bundle adjustment in the largeProceedings of the 11th European conference on Computer vision: Part II10.5555/1888028.1888032(29-42)Online publication date: 5-Sep-2010
https://dl.acm.org/doi/10.5555/1888028.1888032
Simoncini VSzyld D(2003)Theory of Inexact Krylov Subspace Methods and Applications to Scientific ComputingSIAM Journal on Scientific Computing10.1137/S106482750240641525:2(454-477)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1137/S1064827502406415
Hu QLiang G(2002)Acceleration of the non-symmetrized two-level iterationApplied Numerical Mathematics10.1016/S0168-9274(01)00102-741:2(305-323)Online publication date: 1-May-2002
https://dl.acm.org/doi/10.1016/S0168-9274%2801%2900102-7
Hu NGuo XKatz I(1997)Multi-p PreconditionersSIAM Journal on Scientific Computing10.1137/S106482759527936818:6(1676-1697)Online publication date: 1-Nov-1997
https://dl.acm.org/doi/10.1137/S1064827595279368

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents