Leapfrog variants of iterative methods for linear algebraic equations. (English) Zbl 0659.65026
Let be \(x^{(i)}\) the sequence generated by an iterative method to solve the real or complex linear system \(Ax=b\). A leapfrog method is a variant such that \(x^{(i)}\) can be expressed directly in terms of \(x^{(i- 2)}\), and a grand-leap method expresses \(x^{(i)}\) directly by \(x^{(0)}\) without computation of intermediate iterates. These two methods are considered for Richardson’s method, in particular for the Chebyshev case, and for a general second order method. Six different algorithms are presented and discussed, they include the calculation of the required parameters. The advantages of the methods concerning their efficiency on supercomputers are pointed out.
Reviewer: L.Berg
MSC:
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
numerical examples; iterative method; leapfrog method; grand-leap method; Richardson’s method; second order method; supercomputersSoftware:
CHEBYCODEReferences:
| [1] | Adams, L., Iterative algorithms for large sparse linear systems on parallel computers, NASA CR-166027 (1982), NASA Langley Research Center: NASA Langley Research Center Hampton, VA 23665 |
| [2] | Anderssen, R. S.; Golub, G. H., Richardson’s non-stationary matrix iterative procedure, Research Report 304 (1972), Stanford University, Dept. Computer Science |
| [3] | Ashby, S. F., CHEBYCODE: A FORTRAN implementation of Manteuffel’s adaptive Chebyshev algorithm, Research Report No. UIUCDCS-R-85-1203 (1985), Univ. Illinois at Urbana-Champaign, Dept. Computer Science |
| [4] | Ashby, S. F.; Manteuffel, T. A.; Saylor, P. E., A taxonomy for conjugate gradient methods, Report No. UIUCDCS-R-87-1355 (1987) |
| [5] | Chen, So Cheng, Polynomial scaling in the conjugate gradient method and related topics in matrix scaling, Report CS-82-23 (1982), Computer Science Dept., Penn. State Univ: Computer Science Dept., Penn. State Univ University Park, PA 16802 |
| [6] | Chronopoulos, A., A class of parallel iterative methods implemented on multiprocessors, Report No. UIUCDCS-R-86-1267 (November 1986), Univ. of Illinois at Urbana-Champaign, Dept. Computer Science |
| [7] | T.K. Eccles, A method of data management in a simulator used for large Reservoir Models, Proceedings of the Seventh SPE Symposium on Reservoir Simulation, SPE, Dallas, TX, 1983.,; T.K. Eccles, A method of data management in a simulator used for large Reservoir Models, Proceedings of the Seventh SPE Symposium on Reservoir Simulation, SPE, Dallas, TX, 1983., |
| [8] | Elman, H. C.; Streit, R. L., Polynomial iteration for nonsymmetric indefinite linear systems, Research Report 380 (1985), Yale University, Dept. Computer Science |
| [9] | Forsythe, G. E.; Wasow, W. W., NASA CR-166027 (1960), Wiley: Wiley New York |
| [10] | Gautschi, W., On generating orthogonal polynomials, SIAM J. Stat. Sci. Comp., 3, 3, 289-317 (1982) · Zbl 0482.65011 |
| [11] | Golub, G. H.; Welsch, J. H., Calculation of Gaussian quadrature rules, Math. Comput., 23, 221-230 (1969) · Zbl 0179.21901 |
| [12] | Hageman, L. A.; Young, D. M., NASA CR-166027 (1981), Academic Press: Academic Press New York |
| [13] | Johnson, O. G.; Micchelli, C. A.; Paul, G., Polynomial preconditioning for conjugate gradient calculations, SIAM J. Numer. Anal., 20, 2, 362-376 (1983) · Zbl 0563.65020 |
| [14] | Manteuffel, T. A., The Tchebyshev iteration for nonsymmetric linear systems, Numer. Math., 28, 307-327 (1977) · Zbl 0361.65024 |
| [15] | Manteuffel, T. A., Adaptive procedure for estimating parameters for the nonsymmetric Tchebyshev iteration, Numer. Math., 31, 183-208 (1978) · Zbl 0413.65032 |
| [16] | Ortega, J.; Voigt, R. G., Solution of partial differential equations on vector and parallel computers, SIAM J. Stat. Sci. Comp., 149-240 (1985) · Zbl 0644.65075 |
| [17] | Saylor, P. E., Preconditioning symmetric indefinite matrices, (Evans, D. J., Preconditioning Methods: Analysis and Applications (1983), Gordon and Breach: Gordon and Breach New York), 295-319 · Zbl 0767.65022 |
| [18] | Saylor, P. E.; Smolarski S. J., D. C., Computing the roots of complex orthogonal and kernel polynomials, SIAM J. Sci. Stat. Comput., 9 (1988) · Zbl 0637.65042 |
| [19] | Smolarski S. J., D. C., Optimum semi-iterative methods of the solution of any linear algebraic system with a square matrix, Report No. UIUCDCS-81-1077 (December 1981), Univ. Illinois at Urbana-Champaign, Dept. Computer Science |
| [20] | Smolarski S. J., D. C.; Saylor, P. E., An optimum semi-iterative method for solving any linear set with a square matrix, Report No. UIUCDCS-R-85-1218 (July 1985), Univ. Illinois at Urbana-Champaign, Dept. Computer Science |
| [21] | Stiefel, E., (Kernel Polynomials in Linear Algebra and Their Numerical Applications, 49 (1958), National Bureau of Standards Math. Series), 1-22 · Zbl 0171.35703 |
| [22] | Tal-Ezer, H., Polynomial approximation of functions of matrices and applications, NASA Contractor Report 178376, ICASE Report No. 87-63 (1987), Institute for Computer Applications in Science and Engineering, NASA Langley Research Center: Institute for Computer Applications in Science and Engineering, NASA Langley Research Center Hampton, VA 23665 |
| [23] | Wilf, H. S., NASA CR-166027 (1962), Wiley: Wiley New York |
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.
