Skip to main content
SpringerLink
Log in

Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems and applications to the discrete convection-diffusion equation

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Summary.

We study the role of preconditioning strategies recently developed for coercive problems in connection with a two-step iterative method, based on the Hermitian skew-Hermitian splitting (HSS) of the coefficient matrix, proposed by Bai, Golub and Ng for the solution of nonsymmetric linear systems whose real part is coercive. As a model problem we consider Finite Differences (FD) matrix sequences {A n (a,p)} n discretizing the elliptic (convection-diffusion) problem

with Ω being a plurirectangle of Rd with a(x) being a uniformly positive function and p(x) denoting the Reynolds function: here for plurirectangle we mean a connected union of rectangles in d dimensions with edges parallel to the axes. More precisely, in connection with preconditioned HSS/GMRES like methods, we consider the preconditioning sequence {P n (a)} n , P n (a):= D n 1/2(a)A n (1,0) D n 1/2(a) where D n (a) is the suitably scaled main diagonal of A n (a,0). If a(x) is positive and regular enough, then the preconditioned sequence shows a strong clustering at unity so that the sequence {P n (a)} n turns out to be a superlinear preconditioning sequence for {A n (a,0)} n where A n (a,0) represents a good approximation of Re(A n (a,p)) namely the real part of A n (a,p). The computational interest is due to the fact that the preconditioned HSS method has a convergence behavior depending on the spectral properties of {P n -1(a)Re(A n (a,p))} n ≈ {P n -1(a)A n (a,0)} n : therefore the solution of a linear system with coefficient matrix A n (a,p) is reduced to computations involving diagonals and to the use of fast Poisson solvers for {A n (1,0)} n .

Some numerical experimentations confirm the optimality of the discussed proposal and its superiority with respect to existing techniques.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Axelsson, O., Barker, V.: Finite Element Solution of Boundary Value Problems, Theory and Computation, Academic press Inc., New York, (1984)

  2. Bai, Z., Golub, G., M., Ng: ‘‘Hermitian and Skew-Hermitian splitting methods for non-Hermitian positive definite linear systems’’, SIAM J. Matrix Anal. Appl., 24-3, pp. 603–626, (2003)

  3. Beckermann, B., Kuijlaars, A.: ‘‘Superlinear convergence of conjugate gradients’’, SIAM J. Numer. Anal., 39-1, pp. 700–329, (2001)

    Google Scholar 

  4. Bertaccini, D.: ‘‘A circulant preconditioner for the systems of LMF-based ODE codes’’, SIAM J. Sci. Comput., 22-3, pp. 767–786, (2000)

  5. Bertaccini, D.: ‘‘The spectrum of circulant-like preconditioners for some general linear multistep formulas for linear boundary value problems’’, SIAM J. Numer. Anal., 40-5, pp. 1748–1822, (2002)

    Google Scholar 

  6. Bertaccini, D., Golub, G., Serra Capizzano, S.: ‘‘Superlinear convergence of a preconditioned iterative method for the convection-diffusion equation’’, TR SCCM-3-13 Stanford University

  7. Böttcher, A., Grudsky, S.: ‘‘On the condition numbers of large semi-definite Toeplitz matrices’’, Linear Algebra Appl., 279, pp. 285–301 (1998)

    Google Scholar 

  8. Bramble, J.: Multigrid Methods. Pitman Res. Notes in Math. Series, Harlow, (1993)

  9. Buzbee, B., Dorr, F., George, J., Golub, G.: ‘‘The direct solutions of the discrete Poisson equation on irregular regions’’, SIAM J. Numer. Anal., 8, pp. 722–736, (1971)

    Google Scholar 

  10. Chan, R., Chan, T.: ‘‘Circulant preconditioners for elliptic problems’’, J. Numer. Linear Algebra Appl., 1, pp. 77–101, (1992)

    Google Scholar 

  11. Concus, P., Golub, G.: ‘‘Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations’’, SIAM J. Numer. Anal., 10, pp. 1103–1120 (1973)

    Google Scholar 

  12. Concus, P., Golub, G.: ‘‘A generalized conjugate gradient method for nonsymmetric systems of linear equations’’, Lect. Notes Econ. Math. Syst., Springer Verlag, 134, pp. 56–65, (1976)

  13. Concus, P., Golub, G., Meurant, G.: ‘‘Block preconditioning for the conjugate gradient method’’, SIAM J. Sci. Stat. Comp., 6, pp. 220–252, (1985)

    Google Scholar 

  14. Dorr, F.: ‘‘The direct solution of the discrete Poisson equation on a rectangle’’, SIAM Rev., 12, pp. 248–263, (1970)

    Google Scholar 

  15. Elman, H., Schultz, M.: ‘‘Preconditioning by fast direct methods for nonself-adjoint nonseparable elliptic equations’’, SIAM J. Numer. Anal., 23, pp. 44–57, (1986)

    Google Scholar 

  16. Golub, G.H., Van Loan, C.F.: Matrix Computations. The Johns Hopkins University Press, Baltimore, (1983)

  17. Greenbaum, A.: ‘‘Generalization of the field of values useful in the study of polynomial functions of a matrix’’, Linear Algebra Appl., 347, pp. 233–249, (2002)

  18. Hackbusch, W.: Multigrid Methods and Applications. Springer Verlag, Berlin, Germany, (1985)

  19. Holmgren, S., Otto, K.: ‘‘A framework for polynomial preconditioners based on fast transform I: Theory’’, BIT, 38, pp. 544–559, (1998)

  20. Holmgren, S., Otto, K.: ‘‘A framework for polynomial preconditioners based on fast transform II: PDE applications’’, BIT, 38, pp. 721–736, (1998)

  21. Lirkov, I., Margenov, S., Vassilevsky, P.: ‘‘Circulant block factorization for elliptic problems’’, Computing, 53, pp. 59–74, (1994)

  22. Manteuffel, T., Otto, J.: ‘‘Optimal equivalent preconditioners’’, SIAM J. Numer. Anal., 30-3, pp. 790–812, (1993)

    Google Scholar 

  23. Marini, D., Pietra, P.: ‘‘Mixing finite element approximation of a degenerate elliptic problem’’, Numer. Math., 71, pp. 225–236, (1995)

    Google Scholar 

  24. Ng, M., Potts, D.: ‘‘Fast iterative methods for Sinc systems’’, SIAM J. Matrix Anal. Appl., 24-2, pp. 581–598, (2002)

  25. Ng, M., Serra Capizzano, S., Tablino Possio, C.: ‘‘Multigrid methods for symmetric Sinc-Galerkin systems’’, Numer. Linear Algebra Appl., to appear.

  26. Ng, M., Serra Capizzano, S.: ‘‘Multigrid preconditioners for nonsymmetric Sinc-Galerkin systems’’, manuscript, (2004)

  27. Serra Capizzano, S., ‘‘Multi-iterative methods’’, Comput. Math. Appl., 26-4, pp. 65–87, (1993)

  28. Serra Capizzano, S.: ‘‘On the extreme eigenvalues of Hermitian (block) Toeplitz matrices’’, Linear Algebra Appl., 270, pp. 109–129, (1998)

  29. Serra Capizzano, S.: ‘‘An ergodic theorem for classes of preconditioned matrices’’, Linear Algebra Appl., 282 (1998), pp. 161–183.

  30. Serra Capizzano, S.: ‘‘The rate of convergence of Toeplitz based PCG methods for second order nonlinear boundary value problems’’, Numer. Math., 81-3, pp. 461–495, (1999)

    Google Scholar 

  31. Serra Capizzano, S.: ‘‘Convergence analysis of two grid methods for elliptic Toeplitz and PDEs matrix sequences’’, Numer. Math., 92-3, pp. 433–465, 10.007/s002110100331 (2002)

  32. Serra Capizzano, S.: ‘‘Generalized Locally Toeplitz sequences: spectral analysis and applications to discretized Partial Differential equations’’, Linear Algebra Appl., 366-1, pp. 371–402, (2003)

  33. Serra Capizzano, S., Tablino Possio, C.: ‘‘Finite Element matrix sequences: the case of rectangular domains’’, Numer. Alg., 28, pp. 309–327, (2001)

  34. Serra Capizzano, S., Tablino Possio, C.: ‘‘Preconditioning strategies for 2D Finite Difference matrix sequences’’, Electr. Trans. Numer. Anal., 16, pp. 1–29, (2003)

  35. Serra Capizzano, S., Tablino Possio, C.: ‘‘Superlinear preconditioners for Finite Differences linear systems’’, SIAM J. Matrix Anal. Appl., 25-1, pp. 152–164, (2003)

  36. Serra Capizzano, S., Tyrtyshnikov, E.: ‘‘Any circulant-like preconditioner for multilevel matrices is not superlinear’’, SIAM J. Matrix Anal. Appl., 21-2, pp. 431–439, (1999)

  37. Swarztrauber, P.: ‘‘The method of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of Poisson’s equation on a rectangle’’, SIAM Rev., 19, pp. 490–501, (1977)

    Google Scholar 

  38. Wilmott, P., Howison, S., Dewynne, J.: The Mathematics of Financial Derivatives. Cambridge Univ. Press, Cambridge, MA, (1998)

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Matematica, Università ‘‘La Sapienza’‘, P.le A. Moro 2, 00185, Roma, Italy

    Daniele Bertaccini

  2. Department of Computer Science, Stanford University, Gates 2B, CA, 94305, USA

    Gene H. Golub

  3. Dipartimento di Fisica e Matematica, Università dell’Insubria, Via Valleggio 11, 22100, Como, Italy

    Stefano Serra Capizzano

  4. Dipartimento di Matematica e Applicazioni, Università di Milano Bicocca, via Bicocca degli Arcimboldi 8, 20126, Milano, Italy

    Cristina Tablino Possio

Authors
  1. Daniele Bertaccini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gene H. Golub
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stefano Serra Capizzano
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Cristina Tablino Possio
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniele Bertaccini.

Additional information

Mathematics Subject Classification (1991): 65F10, 65N22, 15A18, 15A12, 47B65

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bertaccini, D., Golub, G., Capizzano, S. et al. Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems and applications to the discrete convection-diffusion equation. Numer. Math. 99, 441–484 (2005). https://doi.org/10.1007/s00211-004-0574-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-004-0574-1

Keywords

Search

Navigation