×

s-step iterative methods for symmetric linear systems. (English) Zbl 0669.65021

The authors introduce and study the s-step conjugate gradient (CG) method for solving systems \(Ax=b\) of linear algebraic equations with a symmetric and positive definite system matrix A. In the s-step CG-method, the new iterate \(x_{i+1}=x_ ia^ 1_ ip^ 1_ i+...+a^ s_ ip^ s_ i\) is defined by minimizing the A-energy norm \(\| x_{i+1}-x\|_ A\) of the iteration error over \(\{x_ i+\sum^{s}_{j=1}a^ j_ ip^ j_ i\}\), where the search directions \(p^ j_ i=A^{j-1}r_ i+\sum^{s}_{k=1}b_{i-1}^{(j,k)}p^ k_{i-1}\), \(j=1,2,...,s\), are forced to be A-orthogonal to the preceding s directions, where \(r_ i=f-Ax_ i.\)
From a theoretical point of view, s steps of the classical CG method are identical to one step of the s-step CG-method. However, there are several advantages of the s-step CG-method over the classical CG-method for parallel processing, e.g. a more appropriate data access and the simultaneous calculation of 2s inner products. In analogy to the s-step CG-method, the authors also discuss the s-step conjugate residual method. Stability investigations are made with respect to s. Finally, the authors present some numerical results in order to show the speed-up obtained on the multiprocessor system ALLIANT FX/8.
Reviewer: U.Langer

MSC:

65F10 Iterative numerical methods for linear systems
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akaike, H., On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method, Ann. Inst. Statist. Math. Tokyo, 11, 1-16 (1959) · Zbl 0100.14002
[2] Bauer, F. L.; Householder, A. S., Moments and characteristic roots, Numer. Math., 2, 42-53 (1960) · Zbl 0092.32503
[3] Barkai, D.; Moriarty, K. J.M.; Rebbi, C., A modified conjugate gradient solver for very large systems, IEEE Proc. 1986 Internat. Confer. Parallel Processing, 284-290 (August 1985)
[4] Birman, M. S., Nekotorye ocenki dlja metoda naiskoreisego spuska, Upsehi Matem. Nauk (N.S.), 5, 152-155 (1950)
[5] Concus, P.; Golub, G. H.; O’Leary, D. P., A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, (Bunch, J. R.; Rose, D., Sparse Matrix Computations (1976), Academic press: Academic press New York) · Zbl 0385.65048
[6] Concus, P.; Golub, G. H.; Meurant, G., Block preconditioning for the conjugate gradient method, SIAM J. Sci. Stat. Comput., 6, 1 (1985) · Zbl 0556.65022
[7] A.T. Chronopoulos and C.W. Gear, Implementation of \(s\); A.T. Chronopoulos and C.W. Gear, Implementation of \(s\) · Zbl 0679.65020
[8] A.T. Chronopoulos and C.W. Gear, Implementation of preconditioned \(s Parallel Computing \); A.T. Chronopoulos and C.W. Gear, Implementation of preconditioned \(s Parallel Computing \) · Zbl 0679.65020
[9] Chronopoulos, A. T., A class of parallel iterative methods implemented on multiprocessors, Ph.D. thesis (1986), Department of Computer Science, University of Illinois: Department of Computer Science, University of Illinois Urbana, IL, Tech. Rep. UIUCDCS-R-86-1267
[10] Daniel, J. W., The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal., 4, 10-26 (1967) · Zbl 0154.40302
[11] Elman, H. C., Iterative methods for large, sparse, nonsymmetric systems of linear equations, Ph.D. thesis (1982), Department of Computer Science, Yale University: Department of Computer Science, Yale University New Haven, CT, Tech. Rep. 229
[12] Forsythe, G. E., On the asymptotic directions of the \(s\)-dimensional optimum gradient method, Numer. Math., 11, 57-76 (1968) · Zbl 0153.46004
[13] Golub, G. E.; Van Loan, C. F., Matrix Computations (1983), Johns Hopkins University Press · Zbl 0559.65011
[14] Hestenes, M.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. NBS, 49, 409-436 (1952) · Zbl 0048.09901
[15] Khabaza, I. M., An iterative least-square method suitable for solving large sparse matrices, Comput. J., 6, 202-206 (1963) · Zbl 0131.33901
[16] Meurant, G., The block preconditioned conjugate gradient method on vector computers, BIT, 24, 623-633 (1984) · Zbl 0556.65023
[17] O’Leary, D. P., The block conjugate gradient algorithm and related methods, Linear Algebra Appl., 29, 293-322 (1980) · Zbl 0426.65011
[18] Stiefel, E., Uber einige Methoden der Relaxionsrechnung, Z. Angew. Math. Physik, 3, 1-33 (1952) · Zbl 0046.34104
[19] Saad, Y., Practical use of polynomial preconditioning for the conjugate gradient method, SIAM J. Sci. Stat. Comput., 6, 4 (1985)
[20] Saad, Y., On the Lanczos method for solving symmetric linear systems with several right-hand sides, Math. Comput., 48 (1987) · Zbl 0615.65038
[21] van Rosendale, J., Minimizing inner product data dependence in conjugate gradient iteration, Proc. IEEE Internat. Confer. Parallel Processing (1983)
[22] Varga, R., Matrix Iterative Analysis (1962), Prentice Hall: Prentice Hall Engledwood Cliffs, NJ · Zbl 0133.08602
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.