×

zbMATH — the first resource for mathematics

On the equivalence between the scheduled relaxation Jacobi method and Richardson’s non-stationary method. (English) Zbl 1378.65081
Summary: The scheduled relaxation Jacobi (SRJ) method is an extension of the classical Jacobi iterative method to solve linear systems of equations (\(A u = b\)) associated with elliptic problems. It inherits its robustness and accelerates its convergence rate computing a set of \(P\) relaxation factors that result from a minimization problem. In a typical SRJ scheme, the former set of factors is employed in cycles of \(M\) consecutive iterations until a prescribed tolerance is reached. We present the analytic form for the optimal set of relaxation factors for the case in which all of them are strictly different and find that the resulting algorithm is equivalent to a non-stationary generalized Richardson’s method where the matrix of the system of equations is preconditioned multiplying it by \(D = \operatorname{diag}(A)\). Our method to estimate the weights has the advantage that the explicit computation of the maximum and minimum eigenvalues of the matrix \(A\) (or the corresponding iteration matrix of the underlying weighted Jacobi scheme) is replaced by the (much easier) calculation of the maximum and minimum frequencies derived from a von Neumann analysis of the continuous elliptic operator. This set of weights is also the optimal one for the general problem, resulting in the fastest convergence of all possible SRJ schemes for a given grid structure. The amplification factor of the method can be found analytically and allows for the exact estimation of the number of iterations needed to achieve a desired tolerance. We also show that with the set of weights computed for the optimal SRJ scheme for a fixed cycle size, it is possible to estimate numerically the optimal value of the parameter \(\omega\) in the successive overrelaxation (SOR) method in some cases. Finally, we demonstrate with practical examples that our method also works very well for Poisson-like problems in which a high-order discretization of the Laplacian operator is employed (e.g., a 9- or 17-points discretization). This is of interest since the former discretizations do not yield consistently ordered \(A\) matrices and, hence, the theory of Young cannot be used to predict the optimal value of the SOR parameter. Furthermore, the optimal SRJ schemes deduced here are advantageous over existing SOR implementations for high-order discretizations of the Laplacian operator in as much as they do not need to resort to multi-coloring schemes for their parallel implementation.

MSC:
65F10 Iterative numerical methods for linear systems
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65N06 Finite difference methods for boundary value problems involving PDEs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Jacobi, C., Über eine neue auflösungsart der bei der methode der kleinsten quadrate vorkommenden linären gleichungen, Astron. Nachr., 22, 20, 297-306, (1845)
[2] Yang, X. I.; Mittal, R., Acceleration of the Jacobi iterative method by factors exceeding 100 using scheduled relaxation, J. Comput. Phys., 274, 695-708, (2014) · Zbl 1352.65113
[3] Adsuara, J. E.; Cordero-Carrión, I.; Cerdá-Durán, P.; Aloy, M. A., Scheduled relaxation Jacobi method: improvements and applications, J. Comput. Phys., 321, 369-413, (2016) · Zbl 1349.65114
[4] Markoff, W., Über poynome, die in einem gegeben intervalle möglichst wenig von null abweichen, Math. Ann., 77, 213-258, (1916)
[5] Young, D. M., Iterative solution of large linear systems, (1971), Dover Books on Mathematics, Dover Publications · Zbl 0204.48102
[6] Gutknecht, M. H.; Röllin, S., The Chebyshev iteration revisited, Parallel Comput., 28, 2, 263-283, (2002) · Zbl 0984.68209
[7] Young, D., On Richardson’s method for solving linear systems with positive definite matrices, J. Math. Phys., 32, 1, 243-255, (1953) · Zbl 0055.11202
[8] Frank, W. L., Solution of linear systems by Richardson’s method, J. ACM, 7, 3, 274-286, (1960) · Zbl 0097.11404
[9] Shortley, G., Use of tschebyscheff-polynomial operators in the numerical solution of boundary-value problems, J. Appl. Phys., 24, 4, 392-396, (1953) · Zbl 0050.12404
[10] Richardson, L. F., The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 210, 307-357, (1911) · JFM 42.0873.02
[11] Young, D., On Richardson’s method for solving linear systems with positive definite matrices, J. Math. Phys., 3, 243-255, (1954) · Zbl 0055.11202
[12] Opfer, G.; Schober, G., Richardson’s iteration for nonsymmetric matrices, Linear Algebra Appl., 58, 343-361, (1984) · Zbl 0565.65012
[13] Young, D., Iterative methods for solving partial difference equations of elliptic type, (1950), Harvard University, Mathematics Department Cambridge MA, USA, Ph.D. thesis
[14] Adams, L. M.; LeVeque, R.-J.; Young, D., Analysis of the SOR iteration for the 9-point Laplacian, SIAM J. Numer. Anal., 25, 5, 1156-1180, (1988) · Zbl 0662.65090
[15] Young, D., On the solution of linear systems by iteration, (Proc. Sixth Symp. in Appl. Math., vol. 6, (1956), Amer. Math. Soc.), 283-298
[16] Anderssen, R. S.; Golub, G. H., Richardson’s non-stationary matrix iterative procedure, (1972), Computer Science Dept., Stanford Univ., Tech. Rep. STAN-CS-72-304
[17] Lebedev, V. I.; Finogenov, S. A.; Anderssen, R. S.; Golub, G. H., Richardson’s non-stationary matrix iterative procedure, Zh. Vychisl. Mat. Mat. Fiz., 11, 1, 425-438, (1972), Computer Science Dept., Stanford Univ., Rep. STAN-CS-72-304
[18] Nikolaev, E. S.; Samarskii, A. A., Selection of the iterative parameters in Richardson’s method, Zh. Vychisl. Mat. Mat. Fiz., 12, 4, 960-973, (1972), English translation by J. Berry · Zbl 0249.65042
[19] Lebedev, V. I.; Finogenov, S. A., On construction of the stable permutations of parameters for the Chebyshev iterative methods. part I, Russ. J. Numer. Anal. Math. Model., 17, 5, 437-456, (2002) · Zbl 1032.65059
[20] Einstein toolkit · Zbl 1051.83540
[21] Löffler, F.; Faber, J.; Bentivegna, E.; Bode, T.; Diener, P.; Haas, R.; Hinder, I.; Mundim, B. C.; Ott, C. D.; Schnetter, E.; Allen, G.; Campanelli, M.; Laguna, P., The Einstein toolkit: a community computational infrastructure for relativistic astrophysics, Class. Quantum Gravity, 29, 11, 115001, (2012) · Zbl 1247.83003
[22] LeVeque, R. J., Finite difference methods for ordinary and partial differential equations: steady-state and time-dependent problems, vol. 98, (2007), SIAM
[23] LeVeque, R.-J.; Trefethen, L., Fourier analysis of the SOR iteration, IMA J. Numer. Anal., 8, 3, 273-279, (1988) · Zbl 0648.65028
[24] Brackbill, J. U.; Barnes, D. C., The effect of nonzero product of magnetic gradient and B on the numerical solution of the magnetohydrodynamic equations, J. Comput. Phys., 35, 426-430, (1980) · Zbl 0429.76079
[25] Chorin, A. J., Numerical solution of the Navier-Stokes equations, Math. Comput., 22, 104, 745-762, (1968) · Zbl 0198.50103
[26] Bell, J. B.; Colella, P.; Glaz, H. M., A second order projection method for the incompressible Navier-Stokes equations, J. Comput. Phys., 85, 257-283, (1989) · Zbl 0681.76030
[27] Almgren, A. S.; Bell, J. B.; Szymczak, W. G., A numerical method for the incompressible Navier-Stokes equations based on an approximate projection, SIAM J. Sci. Comput., 17, 2, 358-369, (1996) · Zbl 0845.76055
[28] Cook, G., Initial data for numerical relativity, Living Rev. Relativ., 3, (2000) · Zbl 1024.83001
[29] Baumgarte, T. W.; Shapiro, S. L., Numerical integration of Einstein’s field equations, Phys. Rev. D, 59, 2, (1999) · Zbl 1250.83004
[30] Shibata, M.; Nakamura, T., Evolution of three-dimensional gravitational waves: harmonic slicing case, Phys. Rev. D, 52, 5428-5444, (1995) · Zbl 1250.83027
[31] Tóth, G., The \(\operatorname{\nabla} \cdot B = 0\) constraint in shock-capturing magnetohydrodynamics codes, J. Comput. Phys., 161, 605-652, (2000) · Zbl 0980.76051
[32] Almgren, A. S.; Aspden, A.; Bell, J. B.; Minion, M. L., On the use of higher-order projection methods for incompressible turbulent flow, SIAM J. Sci. Comput., 35, 1, B25-B42, (2013) · Zbl 1264.76032
[33] Centrella, J.; Baker, J. G.; Kelly, B. J.; van Meter, J. R., Black-hole binaries, gravitational waves, and numerical relativity, Rev. Mod. Phys., 82, 3069-3119, (2010) · Zbl 1243.83009
[34] Saad, Y.; Schultz, M., Conjugate gradient-like algorithms for solving nonsymmetric linear systems, Math. Comput., 44, 417-424, (1985) · Zbl 0566.65019
[35] Saad, Y., Iterative methods for sparse linear systems, (2003), Society for Industrial and Applied Mathematics · Zbl 1002.65042
[36] Saad, Y., A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14, 2, 461-469, (1985) · Zbl 0780.65022
[37] Dehghan, M.; Hajarian, M., Improving preconditioned SOR-type iterative methods for L-matrices, Int. J. Numer. Methods Biomed. Eng., 27, 5, 774-784, (2011) · Zbl 1228.65042
[38] Antuono, M.; Colicchio, G., Delayed over-relaxation for iterative methods, J. Comput. Phys., 321, 892-907, (2016) · Zbl 1349.65115
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.