Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-24T08:17:37.888Z Has data issue: false hasContentIssue false
  • English
  • Français

A Non-Krylov Subspace Method for Solving Large and Sparse Linear System of Equations

Published online by Cambridge University Press:  24 May 2016

Wujian Peng  and
Qun Lin
Wujian Peng*
Affiliation:
Department of Math. and Stats. Sciences, Zhaoqing Univ., Zhaoqing, 526061, China
Qun Lin*
Affiliation:
Academy of Math. and System Sciences, Chinese Academy of Sciences, 100081, China
*
*Corresponding author. Email addresses: [email protected] (W.-J. Peng), [email protected] (Q. Lin)
*Corresponding author. Email addresses: [email protected] (W.-J. Peng), [email protected] (Q. Lin)
Get access

Abstract

Most current prevalent iterative methods can be classified into the socalled extended Krylov subspace methods, a class of iterative methods which do not fall into this category are also proposed in this paper. Comparing with traditional Krylov subspace methods which always depend on the matrix-vector multiplication with a fixed matrix, the newly introduced methods (the so-called (progressively) accumulated projection methods, or AP (PAP) for short) use a projection matrix which varies in every iteration to form a subspace from which an approximate solution is sought. More importantly an accelerative approach (called APAP) is introduced to improve the convergence of PAP method. Numerical experiments demonstrate some surprisingly improved convergence behavior. Comparison between benchmark extended Krylov subspace methods (Block Jacobi and GMRES) are made and one can also see remarkable advantage of APAP in some examples. APAP is also used to solve systems with extremely ill-conditioned coefficient matrix (the Hilbert matrix) and numerical experiments shows that it can bring very satisfactory results even when the size of system is up to a few thousands.

Keywords

15A0665F10Iterative methodaccumulated projectionKrylov subspace
Type
Research Article
Information
Numerical Mathematics: Theory, Methods and Applications , Volume 9 , Issue 2 , May 2016 , pp. 289 - 314
Copyright
Copyright © Global-Science Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Axelsson, O., A survey of preconditioned iterative methods for linear systems of equations, BIT, 25:166–187, 1985.CrossRefGoogle Scholar
[2]Axelsson, O., Iterative Solution Methods, Cambridge University Press, 1994.CrossRefGoogle Scholar
[3]Barrett, R., Berry, M., Chan, T. F., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., and Van der Vorst, H., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition. SIAM, Philadelphia, PA, 1994.Google Scholar
[4]Benzi, M., Preconditioning techniques for large linear systems: A survey, Journal of Computational Physics, 182:418–477, 2002.CrossRefGoogle Scholar
[5]Bramley, R. and Sameh, A., Row projection methods for large nonsymmetric linear systems, SIAM J. Sci. Comput., 13(1), 1992.Google Scholar
[6]Cimmino, G., Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, Ric. Sci. Progr. tecn. econom. naz., 9:326–333, 1939.Google Scholar
[7]Datta, B. N., Numerical Linear Algebra and Applications, Brooks/Cole, Pacific Grove, 1995.Google Scholar
[8]Demmel, J. W., Gilbert, J. R., and Li, X. S., An asynchronous parallel supernodal algorithm for sparse gaussian elimination, SIAM J. Matrix Anal. Appl., 20(4):915–952, 1999.Google Scholar
[9]Duff, I. S., Direct methods for solving sparse systems of linear equations, SIAM J. Sci. Stat. Comput., 5:605–619, 1984.Google Scholar
[10]DUFF, I. S., Sparse numerical linear algebra: direct methods and preconditioning, In Duff, I.S. and Watson, G.A., editors, The State of the Art in Numerical Analysis, pp. 27–62. Oxford University Press, 1997.Google Scholar
[11]Freund, R. W. and Nachtigal, N. M., QMR: A quassi-minimal residual method for nonherminian linear systems, Numeri. Math., pp. 315–339, 1991.Google Scholar
[12]Galántai, A., Projectors and Projection Methods, Springer, 2004.Google Scholar
[13]George, A., Nested dissection of a regular finite element mesh., SIAM J. Numer. Anal., 10:345–363, 1973.Google Scholar
[14]Golub, G. H. and Van Loan, C. F., Matrix Computations, Johns Hopkins University Press, Baltimore and London, 1996.Google Scholar
[15]Hackbusch, W., Multi-Grid Methods and Applications, Springer-Verlag, Berlin, 1985.Google Scholar
[16]Hackbusch, W., Iterative Solution of Large Sparse Systems of Equations, Springer-Verlag, New York, 1994.Google Scholar
[17]Paige, C. C. and Saunders, M.A., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., pp. 617–629, 1975.Google Scholar
[18]Peng, W., A lgo-based elimination solver for large scale linear system of equations, Numerical Mathematics– A Journal of Chinese Universities, 36(2):159–166, 2014.Google Scholar
[19]Peng, W. and Datta, B. N., A sparse qs-decomposition for large sparse linear system of equations, In Huang, Y. et al., editor, Domain Decomposition Methods in Science and Engineering XIX, Lecture Notes in Computational Science and Engineering, vol. 78, pp. 431–438. Spring-Verlag, 2011.Google Scholar
[20]Saad, Y., Iterative methods for sparse linear systems (2nd ed.), SIAM., 2003.Google Scholar
[21]Saad, Y. and Schultz, M., Gmres: A generalized minimal residual algorithms for solving non-symmetric linear systems, SIAM J. Sci. and Stat. Comp., pp. 856–869, 1986.Google Scholar
[22]Varga, R.S, Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, NJ, 1962.Google Scholar
[23]Van der Vorst, H. A., BICGSTAB: A fast and smoothly converging varient of the bi-cg for the solution of nonsymmetric linear systems, SIAM J. Sci. and Stat. Comp., pp. 631–644, 1992.Google Scholar
[24]Van der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, 2003.Google Scholar
[25]Young, D. M., Iterative Solution of Large Linear Systems, Academic Press, New York, 1971.Google Scholar