Abstract
A analytic review of major problems and new mathematical and technological discoveries in methods for solving SLAEs is given. This stage of mathematical modeling is a bottleneck because the amount of the required computational resources grows nonlinearly with the increasing number of degrees of freedom of the problem. It is important that the efficiency and performance of computational methods and technologies significantly depend on how well the specific features of the class of application problems—electromagnetism, fluid dynamics, elasticity and plasticity, multiphase filtering, heat and mass transfer, etc. are taken into account. The development of Krylov iterative processes is mainly intended for the construction of two-level algorithms with various orthogonal, projective, variational, and spectral properties, including not only polynomial but also rational and harmonic approximation techniques. Additional acceleration of such algorithms is achieved on the basis of deflation and augmenting approaches using various systems of basis vectors. The goal of intensive studies is to construct efficient preconditioning operators on the basis of various principles: new multigrid schemes and parallel domain decomposition methods, multipreconditioning, nested and alternate triangular factorizations, low-rank and other algorithms for approximating inverse matrices, etc. High-performance and scalable parallelization are based on hybrid programming using internode message passing, multithreaded computations, vectorization, and graphics processing units (GPUs). Modern trends in mathematical methods and software are aimed at the creation of an integrated environment designed for a long lifecycle and massive innovations in important applications.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 INTRODUCTION
Preconditioned iterative methods in Krylov subspaces for solving systems of linear algebraic equations (SLAEs) is an important achievement of computational mathematics in the 20th century. Their significance becomes especially high with the development of supercomputer simulation and solution of interdisciplinary direct and inverse, nonlinear, and nonstationary multidimensional problems with complicated geometric and material properties. Modern requirements for the accuracy of solving problems with real life data lead to superlarge systems (1010–1011 and greater) and huge conditioning numbers (\({{10}^{{14}}}\) and higher) when the standard double precision computations are already on the verge of being available. In this case, the computational cost of solving SLAEs exceeds 80% of the total computational cost for large-scale computer simulations.
Of the most interest for researchers are algebraic systems with sparse matrices that arise as a result of approximation of boundary value problems using finite element and finite volume methods and discontinuous Galerkin algorithms of various orders on unstructured grid (see the review in [1]). In these cases, the portraits or graphs of matrices have an irregular structure, i.e., the distribution of nonzero elements is specified only by their enumeration, and their values are stored in compressed formats, which is an important feature in the implementation of algorithms on modern supercomputers with heterogeneous structure and hierarchical shared memory. The spectral and structure properties of SLAEs are significantly different in different applications—electromagnetism, fluid dynamics, elasticity and plasticity, heat and mass transfer equations, etc., which gives rise to a large variety of algorithms, the development of which goes in the direction of both the study of new iterative processes with various orthogonal, variational and projection properties and the construction of effective preconditioned matrices. A combination of these methodologies determines success in this area. The results of studies are described in the books by Axelsson [2], Elman, Silvester, and Wathen [3], Marchuk and Kuznetsov [4], Saad, [5], Van der Vorst [6], Olshanskii and Tyrtyshnikov [7], Liesen and Strakos [8], the author of his paper [9, 10], and in a huge number of journal publications and conference proceedings.
Speaking about the generalization of Krylov iterative methods, we note that there are various approaches to enriching the corresponding subspaces in which residual or direction vectors for finding new iterative approximations are determined on the basis of various orthogonal of projective principles, including deflation and augmenting algorithms in combination with spectral optimization or least squares principle. It is of interest that there were attempts at constructing “alternatives” to methods in Krylov subspaces, such as Anderson acceleration (which was initially proposed for solving nonlinear systems [11–13]) and Sonneveld subspaces [14]); however, in actual fact they turned out to be variations on the general theme.
The ever increasing stream of literature on methods for solving SLAEs contains a rich palette of ideas for constructing preconditioning matrices that should be easily invertible, increase the convergence rate of iterative algorithms, and ultimately ensure their overall performance. Here multigrid methods, which are asymptotically optimal with respect to order (the amount of computations is proportional to the number of degrees of freedom of the discrete problem), gained a second youth. The methodologies of matrix decomposition have also been significantly developed, including low-rank matrix approximations and nested and alternate triangular factorizations. Various approaches formed a uniform technology for constructing multipreconditioned processes in Krylov subspaces, which are generally multilevel, and additive domain decomposition methods (DDMs), which are the main tool for parallelizing multidimensional problems on multiprocessors. Methods of scalable parallelization and improving the performance of DDMs on supercomputers of heterogeneous architecture with distributed and hierarchical shared memory form the key problem in modern computational algebra [5, 16–19]. Note that the methods for solving SLAEs arising in implicit approximations of initial boundary value problems have some specific features (see the review in [20]). In particular, it was shown in [21] that the choice of initial iterative approximations at each time step using a generalization of the predictor-corrector algorithm can significantly improve the efficiency of computations.
The practical demand for algebraic calculations has led over a half-century history to a huge amount of software, both free and commercial; a fairly complete list of such software can be found in [22], and a classification of algorithms is given in [23]. Here we pay attention to the tools of general importance like SPARSE BLAS and widespread libraries PETSc, HYPRE, MКL INTEL, etc. The international community of experts in computational algebra developed standardized formats for representing matrices and corresponding converters, as well as large collections of matrices from real-life simulation problems that are indispensable for testing and comparative analysis of algorithms. An important trend in recent decades is the transition from concrete libraries and packages of application programs to integrated computational environments, examples of which are DUNE, INMOST, OPEN FOAM, and MATLAB, and the basic simulation system, the concept of which is described in [24] and includes principles of flexible extension of the composition of models and algorithms, as well as the adaption to the evolution of computer architectures, reuse of external software, and coordinated participation of various development groups, which should facilitate the creation of an effective new generation ecosystem with a long lifecycle that joins the communities of mathematicians, software developers, and users from various application domains. On the whole, the high-performance solution of SLAEs for a wide class of practical problems is a promising field of activity for the intellectualization of both research and technological areas.
This paper is organized as follows. In Section 2, we describe the general modern principles of constructing iterative methods in Krylov subspaces, including two-level methods. Section 3 contains a brief review of approaches to constructing preconditioned matrices. Section 4 describes parallelization and performance improving technologies for solving SLAEs, including issues of their software implementation and effective use for simulating real-live processes and phenomena. In the final section, we discuss the prospects of developing the issues under consideration.
2 ORTHOGONAL AND VARIATIONAL PRINCIPLES OF DESIGNING KRYLOV ITERATIVE METHODS
We consider real algebraic systems
with positive semi-definite matrices
among which an important class consists of symmetric positive definite (s.p.d.) matrices with \(\delta > 0\). The SLAEs under examination can be represented in block form
where \({{\Omega }_{q}}\) is the set of indices of matrix rows forming the \(q\)th block row of the matrix \(A\) and \(P\) is its block order.
One of important block structures gives saddle algebraic systems
which arise from the approximation of mixed statements of boundary value problems and in optimization methods. The matrix \(A\) in (3) is invertible if the following conditions are fulfilled:
Along with the original matrix, we will consider preconditioning matrices, which we will denote by the symbol \(B\) with super or subscripts. The choice of preconditioners is based on efficient invertibility and improvement of conditioning of preconditioned matrices of form \({{B}^{{ - 1}}}A\) or \(A{{B}^{{ - 1}}}\), which together should improve the performance of the algorithm software implementation.
A general representation of the stationary iterative process for solving SLAE (1) is the so-called first canonical form
where \({{r}^{n}}\) is the residual vector. It is associated with the second canonical form
where \(T\) is called the transition matrix. A criterion for stopping the iterative process is the fulfillment of the following conditions (for details see [25, 26])
however, it is often assumed that \({{\varepsilon }_{2}} = 0\) for simplicity. The issue of estimating the iterative approximation error \(\left\| {u - {{u}^{n}}} \right\|\) is nontrivial, especially if machine arithmetic precision is taken into account. This issue is considered in a large number of studies (see [8] and references therein).
2.1 Algorithms for Symmetric SLAEs
The inception and the first period of development of iterative methods in Krylov subspaces, which may be dated to 1950–1965, should be attributed to the authors of pioneering works by Lanczos (1950, 1952), Arnoldi (1951), Hestsenes and Stiefel (1951, 1952), Kreig (1954, 1955), Vorob’ev (1958), Faddeev and Faddeeva (1958, 1960), Fridman (1962), Golub (1965), and Varga (1962). The list of subsequent studies is in the hundreds.
We begin the consideration with algorithms for solving symmetric SLAEs with the purpose of giving a uniform view at this intensively developing area of research and discuss important issues of computational performance of methods.
Let the iterative approximation \({{u}^{n}}\) and the corresponding residual vector \({{r}^{n}} = f - A{{u}^{n}}\) be calculated by the formulas
where \({{\alpha }_{k}}\) and \({{p}^{k}}\) are iteration parameters and direction vectors. In this paper, we describe the family of conjugate direction algorithms characterized by various variational and projective properties determined by the corresponding scalar products and norms of vectors
where the exponent is \(\gamma = 0,\;1,\;2\). Let the direction vectors be \({{A}^{\gamma }}\)-orthogonal, i.e.,
where \({{\delta }_{{n,k}}}\) is the Kronecker symbol. Then, the residuals \({{r}^{n}}\) satisfy the relations
This implies that, at the values of the parameters
the functionals \({{\Phi }_{\gamma }}\) take the minimum values
Here and below, the index \(\gamma \) of the coefficients and vectors is dropped for simplicity, and the matrix \(A\) is assumed to be nonsingular for the time being.
There are two ways to satisfy conditions (6). The first one is to use the Lanczos \({{A}^{\gamma }}\)-orthogonalization, which can be written as
where \(\mathop {\bar {\beta }}\nolimits_n \) are chosen from the condition \({{\left\| {{{p}^{n}}} \right\|}_{\gamma }} = 1\). Another way (by Hestenes and Stiefel), which is most widespread due to its stability, uses the two-term recurrence
which, in combination with the formula for the residual in (4), yields other relations for the direction vectors:
Using (4) and (11), we can obtain the property of \({{A}^{{\gamma - 1}}}\)-orthogonality of residual vectors and more convenient (for \(\gamma = 1,\;2)\) formulas for the iteration coefficients
However, \({{\alpha }_{k}}\) in the case \(\gamma = 0\) must be calculated in a different way. Since the exact solution of the SLAE can be represented as the expansion in the basis
the vector error of the iterative approximation and the corresponding residual are written as
Hence, using the \({{A}^{\gamma }}\)-orthogonalization of the vectors \({{p}^{k}}\), we have
Here we used the orthogonality of \({{p}^{n}}\) to the vectors \({{p}^{{n - 1}}}\) and \({{p}^{{n - 2}}}\) and its relation to the vector \(A{{p}^{{n - 1}}}\) in (12). The coefficient \({{\beta }_{{n - 1}}}\) must be calculated by formula (11).
The iterative processes of interest possess optimal properties thus ensuring the minimization of the corresponding functionals \({{\Phi }_{\gamma }}({{r}^{n}})\) of form (7) in Krylov subspaces
In the case \(\gamma = 0,\;1,\;2\), these algorithms are called minimum iteration or minimum error methods (see [8]) and conjugate gradients and conjugate residuals, respectively [5, 9, 27].
The approaches described above admit simple generalization for the SLAEs preconditioned using some s.p.d. matrices \(B\). To preserve the symmetry of systems, this should be done by two-sided preconditioning with the help of the formally introduced matrix \({{B}^{{1/2}}}\). As a result, system (1) takes the form
As a result of applying the conjugate directions formulas to SLAE (17), we obtain after certain transformations the following iterative process for the case \(\gamma = 1,2\):
where the new vectors are related to the old ones by the relations \(\mathop {\hat {p}}\nolimits^n = {{B}^{{ - 1}}}{{p}^{n}}\), \({{\hat {r}}^{n}} = {{B}^{{ - 1}}}{{r}^{n}}\). For the minimum iteration method with \(\gamma = 0\), the parameters \({{\alpha }_{{n - 1}}}{\text{ and }}{{\beta }_{{n - 1}}}\) should be calculated by formulas (15) and (11) in which \({{r}^{k}}{\text{ and }}{{p}^{k}}\) are replaced by \({{\bar {r}}^{k}} = {{B}^{{ - 1}}}{{r}^{k}}\) and \(\mathop {\bar {p}}\nolimits^k = {{B}^{{ - 1}}}{{p}^{k}}\), respectively.
Remark 1. In practice, it is often required to solve a series of SLAEs with the same matrix but successively computed different right-hand sides. In this case, a significant amount of computations can be avoided by memorizing the calculated vectors \({{p}^{k}}\) and \(A{{p}^{k}}\) after solving the first system and somehow using them for expanding the Krylov basis when solving the subsequent SLAEs. These issues are discussed in a large number of papers (see [28] and the list of 157 works therein). However, the significant improvement of “informativeness” of the basis of iterative processes requires further study.
Remark 2. In book [8], the following methodological circumstance was mentioned: Methods in Krylov subspaces are closely related to the problem of moments, which plays an important role in the theory of operators and many applications. The beginnings of this topic were laid by Chebyshev, Markov, and Stieltjes.
In many applications, algebraic systems with symmetric matrices that have a sign definite spectrum are of interest. Such SLAEs can be singular, in particular, consistent or inconsistent. Inconsistent systems have a generalized, rather than classical, solution in the sense of least squares. For these cases, the normal (or pseudoinverse) solution is defined that has the minimum norm and minimizes the residual:
Such a solution always exists and is unique, and its formal representation is obtained using the left Gauss transformation of the original system \(({{A}^{{\text{T}}}}Au = {{A}^{{\text{T}}}}f)\); this representation is
where \({{A}^{ + }}\) is the psedouinverse or generalized inverse matrix of \(A\).
For solving such SLAEs, Saunders with his colleagues (see review [29]) developed the methods SYMMLQ, MINRES, and MINRES–QLP based on the Lanczos \(A\)-orthogonalization, which, due to recurrences (10), can be written in matrix form
where \({{P}_{k}} = [{{p}^{0}},{{p}^{1}},\; \ldots ,\;{{p}^{{k - 1}}}]\). Then, the approximate solution is sought in the form \({{u}^{k}} = {{P}_{k}}{{q}^{k}}\) and is reduced to finding a vector \({{q}^{k}} \in {{\mathcal{R}}^{k}}\) that minimizes the residual
This problem is solved using the LQ- or QR-transformations of the tridiagonal matrix \({{T}_{k}}\) with the orthogonal matrix \(Q\) on the basis of stable Hausholder reflection operations. The results of representative numerical experiments presented by the authors demonstrate good efficiency of the algorithms, and their software implementations are available on the Internet.
The convergence rate of iterations in Krylov-type methods for positive semidefinite SLAEs is characterized by the bound on the number of iterations \(n(\varepsilon )\) required for suppressing the initial error by a factor of \({{\varepsilon }^{{ - 1}}}\):
here \(\kappa \) is generally the effective condition number, which for singular matrices is represented in terms of the minimum nonzero eigenvalue \({{\lambda }_{{\min}}}\).
For symmetric SLAEs, the problem of stable numerical solution was basically solved in the 20th century, including the case of sign indefinite, singular, and inconsistent systems. As for the classical conjugate gradient method, we want to mention Kaporin’s ingenious theory of convergence [30] based on the condition \(K\)-number introduced by him; this number is expressed in terms of the trace and determinant of the matrix.
More specifically, consider the preconditioned conjugate gradient method in the following form:
In this case, it was proved in [31] that the condition
is fulfilled if the number of iterations is
where \(K\) is the condition K-number of the preconditioned matrix \({{B}^{{ - 1}}}A\) defined by
In [32], iterative algorithms were optimized for a number of preconditioners so as to minimize the condition K-number.
2.2 Krylov Algorithms for Asymmetric SLAEs
We continue the description of specific approaches with a wide class of multipreconditioned semiconjugate direction (SCD) algorithms [31]. In the general block form, such iterative methods in Krylov subspaces are written as
Here \(p_{1}^{n},\; \ldots ,\;p_{{{{M}_{n}}}}^{n}\) are the direction vectors constituting at the \(n\)th iteration the matrix \({{P}_{n}}\), and \({{\bar {\alpha }}_{n}}\) is the vector of iteration parameters. For the vectors \(p_{k}^{n}\) in (23), we assume for the time being that only the orthogonality conditions
are fulfilled. However, if we define the coefficients \({{\bar {\alpha }}_{n}} = {\text{\{}}{{\alpha }_{{n,l}}}{\text{\}}}\) by the formulas
then (23) implies the following expressions for the residual functionals:
they attain their minimums in the block Krylov subspaces
at \(\gamma = 1\), and in the case when the matrix \(A\) is skew symmetric also at \(\gamma = 0\). Note that in the case of asymmetric matrices and \(\gamma = 0\), the application of algorithms is actually restricted to SLAEs with the matrices that have a positive definite symmetric part \({{A}_{s}} = 0.5(A + {{A}^{{\text{T}}}})\) because, e.g., for skew symmetric matrices, \((Au,u) = 0\) for \(u = {\text{\{}}1{\text{\}}}\).
The orthogonality property of the direction vectors (24) can be ensured if they are defined using “multipreconditioned” recurrences in which each vector \(p_{l}^{{n + 1}}\) is assigned a specific preconditioning matrix \({{B}_{{n + 1,l}}}\):
If the matrix \(A\) is symmetric, then the recurrence data turn from long ones into two-term data and we obtain the conjugate gradient and conjugate residual methods (for \(\gamma = 0,\;1\), respectively, in multipreconditioned and classical versions). For asymmetric SLAEs, these algorithms are called semi-conjugate gradient or semi-graduate residual (SCG or SCR) methods. In block (multipreconditioned) conjugate direction methods for solving symmetric SLAEs, formulas (23)–(25) remain the same, and the direction matrices \({{P}_{n}}\) are calculated using the two-term recurrences
These formulas, as well as (28), contain “built-in” preconditioning matrices. If we set \({{B}_{{n + 1,l}}} = I\) and \({{M}_{n}} = 1\) for all \(n\), then we obtain the Krylov process in its “pure form” without preconditioning. Note that formulas (28) implement the Gram–Schmidt orthogonalization algorithm, the stability of which can be improved by using the modified Gram–Schmidt (MGS) orthogonalization method [5, 33].
A feature of the algorithms considered here when they are applied to solving ill-conditioned asymmetric SLAEs is their high demand for resources in the sense of the amount of computations and memory when the number of iterations is large. A means for mitigating this drawback is to reduce the number of stored and used direction vectors, which can be achieved using two approaches. The first one is to reduce the recurrence by taking into account only its last \(m\) vectors. The second approach is to periodically restart the process after each \(m\) iterations, i.e., calculate the residual vector from the original equation as at the zero iteration rather than from the recurrence formula:
here \(t\) is the restart index (the further computations up to \(n = {{n}_{{t + 1}}}\) are performed using recurrence (23)). Both approaches significantly slow down the iterative process.
To eliminate this stagnant effect, it is proposed to add a second level of iterations using the least squares method (LSM) [34]. Suppose that we know the restart approximations \({{u}^{{{{n}_{0}}}}},{{u}^{{{{n}_{1}}}}},\; \ldots ,\;{{u}^{{{{n}_{t}}}}}\), \({{n}_{0}} = 0\). Then to correct the iteration vector \({{u}^{{{{n}_{t}}}}}\), which is the initial one for the next restart period of method (23)–(29), we will use the linear combination
in which the vector of coefficients \(\bar {b}\) is found by minimizing the norm \(\left\| {{{r}^{{{{u}_{t}}}}}} \right\|\) of the residual by solving the overdetermined algebraic system
This SLAE can be solved, e.g., using the \(QR\)- or \(SVD\)-decompositions of the matrix \({{W}_{t}}\). The normal solution with the minimum norm \(\left\| {\bar {b}} \right\|\) is found by applying to (31) the left Gauss transformation
A simpler SLAE in the sense of its decreased condition number is obtained by multiplying system (31) by the matrix \(V_{t}^{{\text{T}}}\) on the left:
If \({{V}_{t}}\) is a full rank matrix, then the matrices \(A\) and \({{C}_{t}}\) are simultaneously nonsingular. In this case, we have for the correction vector in (30) the formula \({{{v}}^{{{{n}_{t}}}}} = {{B}_{t}}{{r}^{{{{n}_{t}}}}} \equiv {{V}_{t}}{{(V_{t}^{{\text{T}}}A{{V}_{t}})}^{{ - 1}}}V_{t}^{{\text{T}}}{{r}^{{{{n}_{t}}}}}\), where \({{B}_{t}} = {{V}_{t}}{{\hat {A}}^{{ - 1}}}V_{t}^{{\text{T}}}\) (\(\hat {A} = V_{t}^{{\text{T}}}AV\)) is a low-rank approximation of the matrix \({{A}^{{ - 1}}}\). In this approach, all restart vectors are stored in corrected form, and the corresponding residuals are found by the formula \({{r}^{{{{n}_{t}}}}} = f - A{{u}^{{{{n}_{t}}}}}\). If a matrix under consideration is not invertible, then a generalized inverse matrix is used. Numerous experiments with the use of LSM for accelerating Krylov processes with restarts show its high efficiency.
One more possibility of improving the performance of SCD methods with restarts is to store all direction vectors \({{p}^{n}}\) and the vectors \(A{{p}^{n}}\) obtained during the first restart period and use them in the computations in the subsequent restart periods rather than calculate new vectors \({{p}^{n}}\) and \(A{{p}^{k}}\).
The class of semiconjugate direction method with dynamic multipreconditioning is equivalent in terms of convergence rate to other known algorithms of solving asymmetric SLAEs in Krylov subspaces, among which the most popular one is the generalized minimal residual method GMRES based on Arnoldi orthogonalization and its various versions. This algorithm was proposed by Saad and Schultz in 1986 [5], and it received wide and well-deserved popularity. Among numerous studies of this method, we distinguish the results by Knizhnerman [35] on estimating the error of Arnoldi orthogonalization.
Another principle of constructing Krylov iterative processes for solving asymmetric SLAEs is based on constructing sequences of biorthogonal vectors. In this case, the direction vectors are calculated by short (two-term) recurrences, but two computations of vector-matrix product is required at each iteration step. The biorthogonalization ideas underlie the algorithms BiCG, CGS, and BiCGStab and their various modifications; later, their analogs with \(A\)-biorthogonalization of direction vectors were invented (see review in [36]). The closely related family of induced dimension reduction (IDR) (see [37] and references therein) is based on Sonneveld spaces. Among other approaches, we recommend methods of quasi-minimal residuals and least squares method (LSQR and LSMR) [38]. In recent years, algorithms based on bidiagonal Kreig–Golub–Kahan transformations has also revived (they were originally proposed in 1955 and 1965); their informative study, generalization, and comparative analysis can be found in [25, 39]. Finally, we note flexible conjugate gradient methods (FCG) [40], which are a generalization of the classical CG methods (including preconditioned ones) to the asymmetric case.
3 METHODS OF SLAE PRECONDITIONING
In this section, in the description of algorithms we will discuss at the qualitative level issues of their potential parallelization. A more detailed discussion of technological aspects determining the performance of parallel implementation will be given later.
In addition to the use of a preconditioning matrix considered in (17) and (18), this also can be done by direct preconditioning (left, right, or two-sided) of the original SLAE:
where \(B\), \({{B}_{1}}\), and \({{B}_{2}}\) are nonsingular matrices. Note that if \(A\) is symmetric, then to keep the matrix \({\check{A}}\,\) symmetric, one should set \({{B}_{1}} = B_{2}^{{\text{T}}}\) in the last case. Since the matrices \(\bar {A}\), \(\hat {A}\), or \({\check{A}}\,\) obtained from preconditioned algebraic systems are better conditioned, they should be solved using Krylov iteration formulas in pure form without additional preconditioning (although formally it is not prohibited, and multipreconditioning may be applied using a modification of both the iterative process (28) and the SLAE itself according to (33)).
Among the simple preconditioning methods, we mention scaling and binormalization of matrices. In the first method, a congruent diagonal transformation (\(\tilde {A} = DAD\)) is performed to obtain the unit principal diagonal; the second method is based on leveling the norms of rows and columns of the matrix (see review in [41, 42]). Such approaches may be used as preliminary ones in combination with other preconditioners.
For the block structure of SLAE (2), it seems the most natural to solve it using the Jacobi block method, which in a slightly generalized form is written as
Here \(\theta \in [0,\;1]\) is an iteration (compensating) parameter, and \({{D}_{q}}\) is the diagonal matrix determined by the equation
which is called the compensation or filtering condition (sometimes, the introduction of matrix \({{D}_{q}}\) of form (35) is called lumping). In some cases, the choice of \(\theta \) can be justified and described theoretically, and it helps significantly accelerate the iterative process. There are generalizations of the compensation principle (35) based on a complication of the matrices \({{D}_{q}}\) with banded structure and on the use of several compensating (filtering) vectors [2, 9, 10]:
however, this issue requires further study.
An alternative analog of the block Jacobi method, which belongs to the class of simultaneous displacement iterative or additive algorithms, is the Seidel method and its elaborations—successive over-relaxation and symmetric successive over-relaxation (SOR and SSOR) algorithms. The last method with some modification is also known under the names of alternate triangular, incomplete factorization, and explicit alternate direction scheme (see [2, 9]). These successive displacement or multiplicative methods (the new approximation \(u_{q}^{{n + 1}}\) can be made only after the preceding subvectors \(u_{1}^{{n + 1}},\; \ldots ,\;u_{{q - 1}}^{{n + 1}}\) have been found) have improved convergence rate, and the accelerating compensation principle (35), (36) can be applied to them. However, such algorithms are based on inverting triangular matrices, which is difficult to parallelize. For this reason, in the age of multiprocessor supercomputers, they turned out to be less popular, and we do not consider them in this paper. On the other hand, it was shown in [43] that the application of adaptive successive displacement downstream methods can significantly reduce the number of iterations.
Numerous preconditioning methods have theoretical justification and estimates of the convergence rate (see review in [44–46]). A special case is the dynamic or flexible preconditioning with variable matrices [17, 47–51]. In iterative processes applied to solving SLAEs arising from approximation of boundary value problems on a grid with the characteristic step \(h\) that have the condition number \(O({{h}^{{ - 2}}})\), its magnitude is usually reduced to \(O({{h}^{{ - 1}}})\) due to preconditioning. As a result, the number of iterations in Krylov-type methods is estimated by \(n(\varepsilon ) = O({{h}^{{ - 1/2}}})\). However, it should be taken into account that these asymptotic expressions can include large constants in “bad” problems with a large spread of values of the matrix \(A\) elements.
3.1 Domain Decomposition Algorithms
When grid SLAEs (especially of node type) are solved, each component of the vector to be found is associated with one grid node, and the structure and portrait of the matrix (the configuration of its nonzero elements) are isomorphic to the grid graph (which is directed for asymmetric matrixes and undirected for symmetric ones). In this case, the matrix block structure of form (2) is geometrically represented by the decomposition of the grid computation domain \(\Omega \) into grid subdomains \({{\Omega }_{q}}\) in each of which a subproblem algebraically corresponding to the diagonal block \({{A}_{{q,q}}}\) is formed. Historically, the priority in decomposition methods belongs to the theory of multidimensional boundary value problems since the 19th century, when the solution of differential equations in complex computational domains using the Schwarz alternating method was reduced to examining a sequence of auxiliary problems in overlapping subdomains using the Dirichlet conditions on the introduced internal boundaries. Later, such approaches were generalized on the continuous level in the works by Smelov, Lions, Matsokin, Widlund, Nataf with his colleagues, Vasilevski, Olshanskii, and many other researchers (see reviews of literature in [5, 7, 17–19, 52–57]), and they also were extended to discrete or grid level. In the age of multiprocessor supercomputers, decomposition methods became the main tool for parallelizing computations in the solution of multidimensional initial boundary problems with complex real-life data that require high resolution and speed of computations.
The DDMs may be classified according to three main characteristics. The first one is the dimension of decomposition depending on one, two, or three families of coordinate planes are used for decomposition. The second characteristic is the size of subdomain overlappings, which in a simple case are specified without overlapping, and parameterized overlappings are constructed on the grid level by the layer-by-layer expansion of each subdomain by elementary grid cells. The third direction of DDM development is based on generalizing the types of interface boundary conditions when iterating over subdomains.
On the whole, DDMs are implemented as a two-level iterative process in Krylov subspaces—the upper level is the additive Jacobi–Schwarz block method (34), which for simplicity in its stationary version can be written as
where \({{B}_{1}}\) is the corresponding preconditioner that will actually be used in the Krylov process. At each \(n\)th iteration (37), auxiliary problems are simultaneously or concurrently solved in the subdomains \({{\Omega }_{q}}\); formally, this solution is reduced to inverting the preconditioner blocks \({{B}_{{q,q}}}\). This can be done using direct and iterative methods among which it is natural to choose, in the case of large algebraic systems, preconditioned algorithms in the corresponding Krylov spaces. Note that in the last case we have the problem of solving multiple SLAEs with the same matrix but different right-hand sides, which can be efficiently done by reusing bases of Krylov sunspaces, as was mentioned in remark 1.
From the viewpoint of parallelizing computations on multiprocessors, it is preferable to decompose the computation domain into a greater number of subdomains \({{\Omega }_{q}}\) (\(q = 1,\;2,\; \ldots ,\;P\)) to be able to solve the corresponding subsystems synchronously on \(P\) processors. However, the number of external iterations will obviously grow in this case; this number can be estimated as \(O({{P}^{{1/d}}})\), where \(d\) is the geometric dimension of the domain (assuming that the decomposition forms a \(d\)-dimensional “macronet” consisting of subdomains). The number of external iterations can be reduced by increasing the size of adjacent subdomains overlapping; however, the implementation of each step will be costlier (in practice, the size of overlapping net subdomains has the size of several steps \(h\)).
To accelerate the Krylov-type iterations in DDMs, there are various approaches, which can be interpreted as the application of additional preconditioners, including smoothing preconditioners; for this reason, such methods are sometimes called hybrid (see [58, 59]). By way of example, consider the coarse-grid correction method based on the deflation principle of choosing an initial approximation \({{u}^{0}}\).
Let we have an information basis consisting of vectors \({{{v}}_{1}},\; \ldots ,\;{{{v}}_{m}}\), which compose the matrix \(V = ({{{v}}_{1}}\; \ldots \;{{{v}}_{m}}) \in {{\mathcal{R}}^{{N,m}}}\), \(m < N.\) By choosing an arbitrary vector \({{u}^{{ - 1}}}\), we will seek an initial approximation and the corresponding residual vector in the form
where the vector of unknown coefficients \(c = {{({{c}_{1}},\; \ldots ,\;{{c}_{m}})}^{{\text{T}}}}\) is determined by minimizing the residual \({{r}^{0}}\) from the overdetermined equation
By multiplying both sides of (38) on the left by \({{V}^{{\text{T}}}}{{A}^{\gamma }}\) with the parameter \(\gamma = 0\) or \(\gamma = 1\), we obtain the family of generalized solutions
where the case \(\gamma = 1\) corresponds to the normal solution, which minimizes the Euclidean norms of the residual \({{r}^{0}} = {{r}^{{ - 1}}} - AVc\) and the solution itself \(c\). Hence, we obtain for the corrected residual
which corresponds to the minimum of the functional
It is easy to see that here the vectors \({{{v}}_{s}}\) play the role of direction vectors in Krylov subspaces, i.e., they provide the residual vector \({{r}^{0}}\) with orthogonal and variational properties similar to the properties in the conjugate gradient and conjugate residual methods at \(\gamma = 0\) and \(\gamma = 1\), respectively.
Following this reasoning, we find using \({{r}^{0}}\) the initial direction vector for the conjugate direction method from the orthogonality conditions
The matrix \({{B}_{2}}\) here plays the role of the second preconditioner in addition to \({{B}_{1}}\) in (37), and they both can be used in the subsequent iterations by the formulas of multipreconditioned conjugate directions (see [17]). Note that the exponents of the matrix \(A\) in (40) are chosen in such a way that they ensure the symmetry of \({{B}_{2}}\).
The choice of the basis vectors \({{{v}}_{1}},\; \ldots ,\;{{{v}}_{m}}\) that effectively extend the Krylov subspace is important in many accelerating iterative procedures. For example, the coarse-grid correction algorithm that is used in DDMs is based on the simple case of “geometric” decomposition of the grid domain \({{\Omega }_{q}}\), and its components are 1 or 0, depending on whether or not the corresponding node lies in the \(q\)th subdomain. The further elaboration of this approach is in the transition from piecewise constant basis functions \({{{v}}_{q}}\) to piecewise polynomial functions of higher orders (see [53]).
3.2 Multigrid Methods
In the pioneering works by Fedorenko and Bakhvalov, the multigrid approaches were based on spectral-approximation principles with a separate suppression of the error components corresponding to low and high frequencies. The further development of these approaches took the geometric, algebraic (the most popular name is AMG—Algebraic Multi-Grid) and combinatorial directions (see [5, 56, 60–67]).
These approaches occupy an exceptional place in computational algebra, since they are asymptotically optimal in order, i.e. the required computer resources are proportional to the SLAE size. The most general algebraic methodology is based on the universal principles of matrix preconditioning. The implementation of technologies with various number of nested grids is interpreted as a recursive application of a two-grid algorithm. For simplicity, consider the sequence of nested grids \({{\Omega }_{m}} \subset \; \ldots \; \subset {{\Omega }_{2}} \subset {{\Omega }_{1}}\); i.e., the nodes of the coarser grids are nodes of the “nearest” finer grid \({{\Omega }_{k}}\). We assume that \({{\Omega }_{k}}\) is obtained from \({{\Omega }_{{k + 1}}}\) by “refining by a factor of two,” so that the numbers of grid nodes are related as \({{N}_{k}} \approx {{2}^{d}}{{N}_{{k + 1}}}\), where \(d\) is the domain dimension. To solve the SLAE \(Au = f\) on \(\Omega \), which may be renamed as \({{A}_{1}}{{u}_{1}} = {{f}_{1}}\), a preconditioner \({{B}_{1}}\) is implicitly constructed by approximately solving the system with a specially constructed matrix \({{A}_{2}}\) for the grid \({{\Omega }_{2}}\), and so on; i.e., the process goes in a “loop.”
In the general modern interpretation, the AMG method can be represented by the following stages of iterative solution of the algebraic system \({{A}_{k}}{{u}_{k}} = {{f}_{k}}\) on \({{\Omega }_{k}}\).
1. Given an approximation of the vector \(u_{k}^{n}\), the residual on the “fine” grid \({{\Omega }_{k}}\) is found:
2. For the vector \(r_{k}^{n}\), preprocessing (presmoothing) is performed usually by making several iterations using a simple algorithm. More precisely, this procedure is performed in two steps. At the first step, the direction vector
is calculated, where \({{\hat {S}}_{k}}\) is the operator (matrix) of this presmoothing step. Actually, \({{\hat {S}}_{k}}\) is an approximation of the matrix \({{A}_{k}}\) (a formal representation of the results of several iteration steps of the smoothing method). At the second step, the next (smoothed) approximate solution and the corresponding residual are found:
3. Using the vector \(\tilde {r}_{k}^{n}\) determined on the coarse grid \({{\Omega }_{k}}\), the residual vector \(\tilde {r}_{{k + 1}}^{n}\) on the fine grid \({{\Omega }_{{k + 1}}}\) is formed:
where \({{R}_{k}}\) is a restriction operator (the restriction stage). In the simplest case, this operation is the projection of the vector from the grid \({{\Omega }_{k}}\) onto \({{\Omega }_{{k + 1}}}\).
4. On the fine grid, the direction vector \(\hat {p}_{{k + 1}}^{n}\) is found from the solution of the SLAE
where \({{A}_{{k + 1}}}\) is matrix of the SLAE for the grid \({{\Omega }_{{k + 1}}}\), which in a certain sense inherits the approximation and algebraic properties of the operator \({{A}_{k}}\) on \({{\Omega }_{k}}\). There are various methods for constructing the matrix \({{A}_{k}}\), which is sometimes called the coarse grid correction matrix.
5. The vector \(\hat {p}_{{k + 1}}^{n}\) found from the solution of system (45) is continued from the coarse grid \(\Omega \) to the fine grid \({{\Omega }_{k}}\) (the prolongation stage):
In a certain sense, a consistent definition of the operators above is such that satisfies the relation \(A_{k}^{{ - 1}} \approx {{P}_{k}}A_{{k + 1}}^{{ - 1}}{{R}_{k}}\). If, for example, the matrix \({{A}_{k}}\) is symmetric, then in order to inherit this property on the fine grid \({{\Omega }_{{k + 1}}}\), it is reasonable to use \({{P}_{k}} = R_{k}^{{\text{T}}}\). In particular, this gives the so-called Galerkin approximation \({{A}_{{k + 1}}} = P_{k}^{{\text{T}}}{{A}_{k}}{{P}_{k}}\).
6. For the vector \({{\check{p}_{k}^{n}}}\,\), the corresponding vectors of the approximate solution and residual on the fine grid (residual update) are found by
7. Postprocessing, i.e., repeated smoothing, for the new direction vector and the iterative approximation of the solution on the fine grid \({{\Omega }_{k}}\) is performed with the simultaneous calculation of the new direction vector \(\hat {p}_{k}^{n}\) on the basis of the solution of the auxiliary SLAE with the matrix \({{{\check{S}_{k}}}}\,\) (the repeated smoothing operator, the postsmoothing stage)
similarly to (42).
8. The ultimate direction vector is determined as a result of the first AMG iteration:
where \({{B}_{k}}\) is the preconditioning matrix of this two-grid stage of the method which can be explicitly represented in terms of the smoothing, restriction, coarse-grid correction, and prolongation operators; however, its specific representation is of no importance because the general computations and its implementation are described by formulas (41)–(48). There are a lot of specific versions of the two-grid method, and all of them (in the framework of the stationary iterative process) have the form
which is a two-level iterative process since the operation of multiplying by \(B_{k}^{{ - 1}}\) includes the solution of a SLAE with the matrix \({{A}_{{k + 1}}}\), which is unreasonable to do by the direct algorithm in the case of large \({{N}_{{k + 1}}}\). It is clear that a preconditioned method in Krylov subspaces can be constructed on the basis of algorithm (49).
However, the idea of the multigrid approach is to use the recursive principle: to approximately solve the equation on a coarse grid \({{\Omega }_{{k + 1}}}\), the methods described above are applied on the coarser grid \({{\Omega }_{{k + 2}}}\), and so on. The computations on each grid \({{\Omega }_{k}}\) by formulas (41)–(48) may be repeated a prescribed number of times \(\gamma \), which can be written as a generalization of relation (49):
In practice, the number of such repetitions is \(\gamma = 1\) or \(\gamma = 2\). In the first case, the computation scheme is called \(V\)-loop, and in the second case it is W-loop. In [64, 65], an elaboration of this approach was proposed: K-loop, in which at \(\gamma = 2\) a Krylov-type (rather than stationary) iterative process is used (more specifically, the “flexible” conjugate gradient FCG method described in [40]). In the last formula, it should be taken into account that the preconditioner \({{B}_{k}}\) is expressed recursively for \(k = 1,\;2,\; \ldots ,\;m - 1\), and on the last \(m\)th grid SLAE (45) with the matrix \({{A}_{{m + 1}}}\) is solved directly (by a direct or iterative method).
Specific implementations of multigrid approaches, which have already became classical, differ in the way of choosing the matrix operators determining the successive stages of the computation scheme described above.
3.3 Incomplete Factorization Algorithms
The most classical methods of SLAE preconditioning are numerous explicit and implicit matrix factorization methods; a thorough analysis of such methods without parallelization aspects can be found in [10]. Modern approaches to these technologies, including promising approximations of matrices that are inverse of triangular factors in incomplete matrix decompositions are described in [68–70] and references therein.
The typical form of easily invertible preconditioned matrix is obtained by the approximate factorization
Here \(L\) and \(U\) are the lower and upper triangular parts of the original matrix \(A = D + L + U,\) and \(D\) is a block diagonal or diagonal (in a special case) matrix. On the basis of the general requirement \(B \approx A\), the block diagonal matrix \(G\) is constructed using the relation
where the overscore above a matrix denotes its banded approximation.
Based on formulas (51) and (52), various successive symmetric upper relaxation methods are constructed (in this case, \(G = 2{{\omega }^{{ - 1}}}D)\), where \(\omega \) is an iteration parameter; another group of methods is explicit and implicit incomplete factorization, which are analyzed in books [2, 5, 10, 68] and in special reviews [51, 69, 70]. A large family of algorithms is based on the incomplete LU-factorization of the original matrix, which in the symmetric case is reduced to the approximate Cholesky decomposition. The quality of the matrix approximation and the convergence rate are improved due to “compressing” the matrix factors; however, each iteration step becomes costlier.
A similar approach, but focused on parallelization, is to construct a sparse approximation of the inverse matrix, thus eliminating the need to solve triangular systems at each iteration. These methods were studied in both pointwise and block versions. Novel results in this direction were obtained by Eremin, Kaporin, Kolotilina, Kon’shin, and other researchers in [31, 32, 71, 72]. Another promising direction of research is based on the factorization (including approximate one) of hierarchical matrices in HSS formats using low-rank block structures in the LU decomposition (see [73, 74]).
Finally, pay attention to one more promising family of algorithms for constructing preconditioners that are based on network programming or graph transformation methods (see [75–77]). An important point is that as traditionally the incomplete triangular decomposition of matrices is realized for nonsingular matrices, now there are its modifications for positive semidefinite cases.
A general approach to speeding up the iterations is based on the compensation principle or matching row sums, which is to find a matrix \(G\) in (51), (52) such that
on a given set of \(m\) trial vectors (see [49, 78] and references therein). In some works, this method is also called filtering.
To satisfy condition (53), the matrix \(G\) is transformed to the form
where \(\theta \in \left[ {0,1} \right]\) is a compensating parameter and \(S\) is a block diagonal matrix formed on the basis of the condition
Among the incomplete factorization methods for solving network SLAEs, implicit methods are the fastest; they are based on triadiagonal matrix algorithms for solving auxiliary tridiagonal systems. Such algorithms can be effectively parallelized on multiprocessors using a multithreading implementation of recursive triadiagonal matrix procedures based on the reduction of original SLAEs or on bordering methods. Note that in [57] a two-thread block version of alternate-triangular matrix factorization method was proposed, in which each factor is not a lower or upper triangular matrix but rather consists of block rows of different orientations—some of them are lower triangular and the others are upper triangular; this decomposition is called twisted decomposition (see review in [27]).
If \(A\) is a symmetric matrix, i.e., \(D = {{D}^{{\text{T}}}}\) and \(L = {{U}^{{\text{T}}}}\), then it is natural to choose symmetric matrices \(G\) and \(B\) and use two-sided preconditioning for the original SLAE with preserving the symmetry of the final system:
The preconditioned matrix \(\bar {A}\) can be reduced by simple transformations to the form
in which the vector-matrix multiplication can be implemented in the form
in many cases, this saves a significant amount of computations. Note that the matrix representations (56)–(58) also hold without the requirements \({{L}_{B}} = U_{B}^{{\text{T}}}\) and \({{L}_{G}} = U_{G}^{{\text{T}}}\); i.e., these formulas also apply to asymmetric SLAEs.
The direct inversion of triangular matrices used in the algorithms described above is poorly parallelized. There are special tricks for mitigating this drawback (e.g., see [79] and the review in [80]). We consider another approach that uses alternate-triangular matrices \(\hat {L}\) and \(\hat {U}\) instead of \(L\) and U, which have nonzero elements only on the left of the principal diagonal in some rows and nonzero elements only on the right in the other rows. We illustrate the construction of such preconditioners by way of a block tridiagonal matrix
In this case, we define the alternate-triangular matrices by
In this case, \(A = D + \hat {L} + \hat {U};\) therefore, the incomplete factorization formulas (51)–(58) for determining the preconditioner \(B\) remain valid. Only \(L\) and \(U\) should be replaced by \(\hat {L}\) and \(\hat {U}\), respectively. In this case, the tridiagonal blocks of the matrix \(\bar {G} = \{ {{\bar {G}}_{i}}\} \) are found by formulas similar to (28) and (29) but using opposite recursions (block tridiagonal method [25]), which we write for an arbitrary odd \({{N}_{x}} = 2m + 1\):
where \({{S}_{i}}\) are diagonal matrices for \(l = 1\) and tridiagonal for \(l = 2\).
When the matrix \(\bar {B}\) is used as a preconditioner for an iterative process, the following auxiliary system must be solved at each step:
Its solution can be found from the successive relations
which are implemented by twisted decomposition by the formulas
In recurrences (61) and (62), the computations with increasing index \(i\) and with its decreasing may be called forward and backward recursions, respectively. It is clear that they can be executed simultaneously in two threads. This limited parallelism is based on the alternate-triangulation (60) for the matrices \(L\) and \(U\). This approach can be generalized for the case of \(P\)-alternate triangulation; i.e., we can define matrices \(\hat {L}\) and \(\hat {U}\) satisfying the condition \(\hat {L} + \hat {U} = L + U\) as consisting of \(P\) block rows each of which successively changes the triangulation type. Formulas for the block tridiagonal matrix algorithm (61), (62) are more complicated, but they can be parallelized to \(P\) processors.
For example, matrix (59) corresponds to the five-point Laplace equations on a rectangular grid with \(N = {{N}_{x}} \cdot {{N}_{y}}\) nodes. In this case, \({{D}_{i}}\) are tridiagonal blocks and \({{L}_{i}}\) and \({{U}_{i}}\) are diagonal blocks. In the case of three-dimensional problems on a box grid with \(N = {{N}_{x}} \cdot {{N}_{y}} \cdot {{N}_{z}}\) nodes, the matrix \(A\) can be represented in block tridiagonal form (59) in which each diagonal block \({{D}_{k}}\) has the size \(N = {{N}_{x}} \cdot {{N}_{y}}\) and is a matrix of the same structure as (59).
The elaboration of the above approaches for solving SLAEs on three-dimensional grids received the name of nested factorization methods; they were proposed in 1983 by Appleyard and Cheshire and later studied by many researchers (see [57, 82, 83] and references therein). Let the matrix \(A\) have the form
where \(D\) is a diagonal and \({{L}_{k}}\) and \({{U}_{k}},k = 1,2,3\), are lower and upper triangular matrices. Let us find the preconditioning matrix \(B\) using the recursive factorization (51):
as a result, we obtain
Depending on the definition of M, different preconditioners \(B\) can be formed. We consider a simple case when matrix (63) corresponds to the seven-point approximation of the Dirichlet problem for the Poisson equation in a box on a box grid. Then, in the case of natural ordering of the nodes, the matrices M, \(T\) and \(P\) can be made diagonal, tridiagonal, and five-diagonal, respectively, and the preconditioner can be found by the formulas
Here \({{\theta }_{2}}\) and \({{\theta }_{3}}\) are iteration (relaxing) parameters, and \({{S}_{2}}\) and \({{S}_{3}}\) are diagonal matrices determined from the conditions of matching row sums similarly to how this was done above:
Note that instead of (67) we may use matching column sums rather than row sums (see [83] and references therein):
The three-level nested factorization considered above can be structurally simplified by reducing it to the two-level one. To this end, we rewrite the original matrix \(A\) (63) in the form
In this case, \({{D}_{3}}\) is a block diagonal matrix with five-diagonal blocks \({{D}_{{3,i}}}\) of size \({{N}_{y}}{{N}_{z}}\) each of which corresponds to a plane problem in the section \(x = {\text{const}}\) and has the same structure as the matrix \(A\) in (59). Then, the matrix \(P\) in (64) is defined by the formula
which corresponds to the definition \({{L}_{3}}{{P}^{{ - 1}}}{{U}_{3}} = 0\) in (64). Note that \({{L}_{3}}\) and \({{U}_{3}}\) can be defined as alternate-triangular matrices, and then the algorithm implementation can be parallelized using twisted decomposition.
3.4 Solving Saddle SLAEs
Consider a SLAE with a saddle matrix
where \(A \in {{\mathcal{R}}^{{N,N}}}\), \(D \in {{\mathcal{R}}^{{{{N}_{1}},{{N}_{1}}}}}\), \(C \in {{\mathcal{R}}^{{{{N}_{2}},{{N}_{1}}}}}\), \(N = {{N}_{1}} + {{N}_{2}}\), \(f \in {{\mathcal{R}}^{{{{N}_{1}}}}}\), and \(p,g \in {{\mathcal{R}}^{{{{N}_{2}}}}}\). The matrix \(D\) is assumed to be symmetric and positive semidefinite. A necessary and sufficient condition for the nonsingularity of \(A\) is \(\ker (D) \cap \ker (C) = {\text{\{}}0{\text{\}}}\), and a sufficient condition is the positive definiteness of \(D\) on \(\ker (C)\) and \(\ker ({{C}^{{\text{T}}}}) = {\text{\{}}0{\text{\}}}\), which we assume to be fulfilled.
Problems with a saddle point often arise in mathematical formulations in modeling, including initial boundary mixed formulations for differential classical or generalized equations, optimization problems, and computational algebra (see [84–87] and references therein). We focus on methods for solving saddle SLAEs with large sparse matrices that arise in grid approximations of multidimensional boundary value problems in many applications—electromagnetism, fluid dynamics, elasticity, plasticity, multiphase filtering in porous media, in optimization problems, etc.
Due to special features of the block structure of saddle algebraic systems, methods for their solution are studied in numerous works, e.g., see the reviews by Golub and his colleagues [84], Brezzi [85], Vassilevski [72], and Notay [86], book by Bychenkov and Chizhonkov [87], series of papers by C. Greif and his colleagues (including the case of asymmetric saddle SLAEs [68, 85]), and Arioli with coauthors [25, 75] (also see the reviews in [90–92]).
Note that without loss of generality the saddle SLAE can be considered in the form
Indeed, if we take a particular solution of system \(C\hat {u} = g\), then the vector \(u = \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{u} + \hat {u}\), which is a solution of SLAE (70), satisfies the system
Note that any solution of SLAE (71) simultaneously satisfies the system
where \({v},\tilde {f} \in {{\mathcal{R}}^{N}}\), and \({{K}_{0}} \in {{\mathcal{R}}^{{{{N}_{1}},{{N}_{1}}}}}\) is an arbitrary nonsingular matrix. Since the last system is formally a regularization (or generalization) of SLAE (71), we below discuss algorithms for solving Eq. (72).
Using the Schur complement
the matrix of system (72) is factorized as
If the matrices \(\bar {D}\) and \(S\) are replaced by their approximations (preconditioners) \({{B}_{d}}\) and \({{B}_{s}}\), then we obtain a preconditioner for the matrix \(B\) in the form of incomplete block factorization
A somewhat coarser approximation when only one (left or right) factor is used in (73) gives an incomplete block triangular preconditioning with the matrix
or the incomplete Uzawa preconditioner
The implementation of each step of the corresponding iterative processes can be divided into several stages at which only one block component of the desired solution is recalculated (for this reason, these methods are sometimes called segregative). In a slightly generalized form, we represent such a stationary algorithm (without the Krylov acceleration) by the following three stages (see [83, 85, 86]):
Here \(Q_{d}^{{(1)}}\) and \(Q_{d}^{{(2)}}\) are approximations of inverse or generalized inverse matrix of the preconditioner \({{B}_{d}}\). In particular, if \(Q_{d}^{{(1)}} = B_{d}^{{ - 1}}\), \(Q_{d}^{{(2)}} = 0\) or \(Q_{d}^{{(1)}} = 0\), \(Q_{d}^{{(2)}} = B_{d}^{{ - 1}}\), then we obtain from (76) the Uzawa algorithm with the preconditioner \({{B}_{3}}\) defined in (75) (in this case, the third stage is omitted, i.e., \(u_{d}^{{n + 1}} = \hat {u}_{d}^{{n + 1}}\)) or the incomplete block triangular preconditioning with the matrix \({{B}_{2}}\) defined in (74) (in this case, the first stage in (76) is omitted and \(u_{d}^{{n + 1}} = u_{d}^{n}\)).
If the matrix \({{Q}_{d}} = Q_{d}^{{(1)}} + Q_{d}^{{(2)}} - Q_{d}^{{(2)}}\bar {D}Q_{d}^{{(1)}}\) is singular, then the iterative process (76) is associated with the preconditioner
In this case, for \(Q_{d}^{{(1)}} = Q_{d}^{{(2)}} = B_{d}^{{ - 1}}\) (77) implies the so-called symmetrized Uzawa method with the preconditioned matrix
A promising block diagonal preconditioner for solving SLAE (72) is
where \({{K}_{1}}\) and \({{K}_{2}}\) are symmetric nonsingular matrices.
The eigenvalues and eigenvectors of the preconditioned matrix \(\bar {A} = B_{6}^{{ - 1}}\tilde {A}\) from the “disturbed” SLAE (72) are determined by the eigenvalue problem
which in componentwise form is written as
The analysis of this eigenvalue problem yields interesting results for various special cases. In particular, it was shown in [81, 82] that unique spectral properties of the matrix \(\bar {A}\) are obtained if the block \(\tilde {D}\) is strongly singular, which is important for algorithms designed for solving systems of Maxwell equations. For example, we have the following results.
Proposition 1. Let \({{B}_{6}}\) be an spd matrix and \({\text{\{}}{{z}_{i}},\;i = 1,\;2,\; \ldots ,\;{{N}_{1}} - {{N}_{2}}{\text{\}}}\) be a basis of the kernel of the matrix \(C\). Then, the preconditioned matrix \(B_{6}^{{ - 1}}\tilde {A}\) has \({{N}_{1}} - {{N}_{2}}\) linearly independent vectors \((z_{i}^{{\text{T}}}0) \in {{\mathcal{R}}^{N}}\) associated with \({{N}_{1}} - {{N}_{2}}\) multiple eigenvalue \(\lambda = 1\).
Proposition 2. Let \({{K}_{1}} = {{K}_{2}} = K\), and let \(\tilde {D}\) be a symmetric positive semidefinite matrix with the kernel dimension equal to \(r\). Then, \(\lambda = 1\) is an eigenvalue of the matrix \(B_{6}^{{ - 1}}\tilde {A}\) with the multiplicity \({{N}_{1}}\), \(\lambda = - 1\) is an eigenvalue of multiplicity \(r\), and the other \({{N}_{2}} - r\) eigenvalues lie in the interval \(\lambda \in ( - 1,\;0)\) and satisfy the relation
where \(\mu \) are \({{N}_{2}} - r\) positive generalized eigenvalues
Let \({\text{\{}}{{z}_{i}},\;i = 1,\;2,\; \ldots ,\;{{N}_{1}} - {{N}_{2}}{\text{\}}}\) be a basis of the kernel of \(C\), \({\text{\{}}{{x}_{i}},\;i = 1,\;2,\; \ldots ,\;{{N}_{2}} - 2{\text{\}}}\) be a basis of the kernel of \(\tilde {D}\), and \({\text{\{}}{{y}_{i}},\;i = 1,\;2,\; \ldots ,\;{{N}_{2}} - r{\text{\}}}\) be the set of linearly independent vectors complementing \(\ker (\tilde {D}) \cup \ker (C)\) in the basis \({{\mathcal{R}}^{{{{N}_{1}}}}}\). Then, \({{N}_{1}} - {{N}_{2}}\) vectors \(({{z}_{i}},0)\), \(r\) vectors (\({{x}_{i}}\), \({{K}^{{ - 1}}}C{{x}_{i}}\)), and \({{N}_{2}}\) – \(r\) vectors (\({{y}_{i}}\), \({{K}^{{ - 1}}}{{y}_{i}}\)) are linearly independent eigenvectors corresponding to the eigenvalues \(\lambda = 1\), and \(r\) vectors (\({{x}_{i}}\), \({{K}^{{ - 1}}}{{x}_{i}}\)) are the eigenvectors corresponding to the eigenvalues \(\lambda = - 1\).
On the whole, the presence of different matrices \({{K}_{0}}\), \({{K}_{1}}\), and \({{K}_{2}}\) in the preconditioner \({{B}_{6}}\) provides wide opportunities for constructing efficient algorithms in particular cases.
We consider a family of iterative methods for solving saddle symmetric SLAEs with the matrix \(\tilde {A}\) defined by (72); this family is based on the efficient Golub–Kahan \(G - K\)-bidiagonalization, which was originally proposed for the singular decomposition of rectangular matrices but later was successfully used for solving algebraic systems, including the case of block saddle structure, in the works by Saunders, Arioli, Greif, and other researchers.
Without loss of generality, we write the SLAE under examination in the form
It is easy to verify that, if the function \(u\) in (72) is replaced by \(u + {{\tilde {D}}^{{ - 1}}}f\), then this system takes form (80) with the right-hand side \(g = - C{{\tilde {D}}^{{ - 1}}}f\). It is assumed that \(\tilde {D}\) and \(K\) in (80) are spd matrices and \({{N}_{1}} \geqslant {{N}_{2}}\).
The \(G - K\)-bidiagonalization method is based on the construction of \(\tilde {D}\)-orthogonal vectors \({{{v}}_{k}}\) and \(K\)-orthogonal vectors \({{q}_{k}}\) that satisfy the conditions
where \(V = [{{{v}}_{1}},\; \ldots ,\;{{{v}}_{{{{N}_{1}}}}}] \in {{\mathcal{R}}^{{{{N}_{1}},{{N}_{2}}}}}\), \(Q = [{{q}_{1}},\; \ldots ,\;{{q}_{{{{N}_{1}}}}}]\), and \(B \in {{\mathcal{R}}^{{{{N}_{2}},{{N}_{2}}}}}\) is a two-diagonal matrix
By introducing new unknown functions
and multiplying system (80) by the block diagonal matrix block-diag(\({{V}^{{\text{T}}}},{{Q}^{{\text{T}}}}\)), we obtain
It follows from (83) that the vector \(u\) depends on \({{N}_{2}}\) columns of the matrix \(V\) because \({{z}_{2}} = 0\). Thus, SLAE (83) is reduced to the form
Hence, we put
to obtain the initial vector \({{{v}}_{1}}\):
The further vectors \({{{v}}_{n}}\), \({{q}_{i}}\), and the elements \({{\alpha }_{i}}\), \({{\beta }_{i}}\) of the matrix \(B\) are calculated from the recurrences (\(n = 1,\;2,\; \ldots \))
The successive approximations \({{u}^{n}}\), according to (82), are found from the first \(n\) columns of the matrix V, i.e.,
where \(z_{1}^{j}\) are the components of the vector \({{z}_{1}}\) in (84) calculated by the formulas
We omit the details of derivation of these formulas (see [87]) and only present the final recurrences for the iterative solution
where \({{d}_{n}}\) is the \(n\)th column of \(D = Q{{B}^{{ - 1}}}\). Note that the algorithm just described has the following optimization properties: at each \(n\)th step, the iterative approximation error has the minimum
As is mentioned in [71], this method has high convergence rate in the case of SLAEs arising in finite element approximations of continuous multidimensional saddle problems, i.e., in mixed statements. An important factor is that at each iteration algebraic subsystems with the matrices \(\tilde {D}\) and \(K\) must be solved; in a certain sense, these matrices play the role of preconditioners. Their approximate inversion actually leads to two-level iterative processes in certain subspaces.
4 PARALLELIZATION AND PERFORMANCE ISSUES OF ITERATIVE METHODS
The modern understanding of algorithm quality includes two main characteristics—mathematical efficiency and performance of implementation on a particular supercomputer architecture. The first characteristic includes the construction and optimization of iterative methods with a high convergence rate and theoretical estimates of the required computational resources (the number of arithmetic operations and amount of memory). The second characteristic is purely practical—it is determined by the actual execution time of the algorithm for a certain class of problems, which depends on the scalability of the algorithm parallelization and on the programming technology on a specific computer platform.
The SLAEs of greatest interest for us have large size (108–1011) and sparse matrices with large condition numbers (1012–1015) and irregular structure. This not only leads to a large number of iterations, but also forces one to work with systems of distributed and hierarchical shared memory and also significantly speeds down data access.
The main quantitative characteristic of parallelization is the acceleration of computations
where \({{T}_{p}}\) is the time of solving the problem on \(p\) processors, which is the sum of data exchange time and arithmetic operations execution time; in turn, these times are found by the approximate formulas
Here \({{\tau }_{a}}\) and \({{N}_{a}}\) are the average time of an arithmetic operation execution and their total number, respectively, \({{N}_{t}}\) is the number of data exchanges, \({{\tau }_{0}}\) and \({{\tau }_{c}}\) are the waiting time and the time of sending one number, respectively, and \({{N}_{c}}\) is the average size of one communication.
Machine constants satisfy the inequalities \({{\tau }_{0}} \gg {{\tau }_{c}} \gg {{\tau }_{0}}\); therefore, for the algorithms to be constructed, we have obvious recommendations: try to minimize the size of communications, and make data exchanges in large portions, i.e., pre-accumulate data buffers. These conclusions are all the more true because interprocessor data transfers not only slow down the computational process but also are the most energy-consuming operations, and this becomes a significant factor in the costs of operating a supercomputer [93].
The strategy of parallelizing large grid SLAEs arising as a result of approximation of multidimensional boundary value problems is based on hybrid programming and additive domain decomposition methods with two-level iterations in Krylov subspaces. The upper level iterations (over subdomains) are performed using the message passing interface MPI between processes each of which solves (simultaneously) an algebraic subsystem in the corresponding subdomain. At each iteration, the values of approximate solutions on the interface between subdomains are exchanged. Naturally, all matrix and vector data for the subsystems are preliminary distributed between processes. The solution of the SLAE in each subdomain is parallelized using multithreading computations (like OpenMP) on multicore processors with shared memory. Additional acceleration can be achieved by vectorizing operations (AVX-like instruction sets based on SIMD (Single Instruction Multiple Data) technologies (see reviews in [18]). Unfortunately, presently there are no ready-to-use software development systems with automatic parallelization of algorithms; hence the success in computations speedup and scalability significantly depends on the skills of the programmer.
Note that the traditional block Jacobi–Schwarz methods underlying parallel domain decomposition algorithms are based on the spectral optimization of iterative processes. A possible alternative to them are projection block Cimmino methods [9, 94], which still are not sufficiently well studied and rarely used in practice.
From the parallelization viewpoint, implicit alternating direction or Peaceman–Rachford methods (see [90] and the review in [10]), which were intensively developed in the 1960–1970s seem promising. They have a record convergence rate of iterations for model grid boundary value problems. In recent decades, this direction has found a second wind in connection with the development of rational approximations in Krylov subspaces (see [95]), including the solution of Lyapunov and Sylvester matrix equations. Note that in [93] a method for increasing the degree of parallelization on the basis of expanding rational functions in partial fractions was proposed.
Computations can be significantly accelerated by using variable precision arithmetic. Traditionally, the solution of large SLAEs uses double precision arithmetic in which floating point numbers are represented by 64 bits; however, for extremely poorly conditioned matrices, quad precision (128 bits) is required. By contrast, at certain stages of the algorithm, single and even half precision (32 and 16 bits, respectively), which is significantly faster may be used. This approach is quite natural at first iterations when the error of the approximate solution is relatively high. Another option of using low precision is in DDMs when solving auxiliary problems in subdomains. It should be taken into account that such tricks require a thorough analysis of numerical errors of the method to ensure the stability of computations as a whole.
A further reserve for improving performance is code optimization, which can be achieved by using high-quality computational tools (e.g., SPARSE BLAS), by using various compiler options, and special properties of a particular supercomputer platform. In recent decades, a large number of high-quality software libraries for computational algebra have been developed (PETSс, HYPRE, MKL INTEL, and others, see the review in [22, 23]). Also pay attention to the works performed in the All-Russian Research Institute of Experimental Physics, Russian Federal Research Center (Sarov) [96] and to projects on integrated computational environments DUNE [97], INMOST [98], and BSM [1, 24].
The creation, maintenance, and development of mathematical methods and software for the efficient solution of SLAEs is a continuous science-intensive technological process, which includes regular experimental research that requires intelligent means of support, such as systems for automation of verifying and testing algorithms and their implementations, collections of problems (such as popular Sparse Matrix Collections offered by various developers) and numerous demo and training versions of software (in addition to traditional monographs, textbooks, and user guides with recommendations on the application of various algorithms for solving various practical problems).
5 CONCLUSIONS: PROBLEMS AND PROSPECTS OF DEVELOPING ITERATIVE PROCESSES
From the systems point of view, the high-performance solution of SLAEs is a widely demanded area of intellectual activity that is far from being limited by writing and justifying formulas of the algorithm; it also includes statements of new practical problems or theoretical ideas, technological aspects of software implementations, and issues of their effective application in supercomputer experiments.
New practical challenges of mathematical modeling will drastically increase the demand for solving interdisciplinary and inverse high resolution problems on real-life data, which makes the high-performance solution of SLAEs with tens or hundreds of billions of degrees of freedom and extremely poor conditioning. In recent decades, the computational algebra methods have been rapidly developing both theoretically and experimentally, and promising directions have developed here: low-rank approximations of matrices, including rational approximations, tensor methodologies graph-theoretic and combinatorial approaches, aggregation and segregation methods; moreover, novel ideas in traditional matrix factorizations, algebraic decompositions, multigrid technologies, etc. are appearing.
Another important factor is the ongoing accumulation of a vast number of various problems (interdisciplinary, methodological, practical, typical, and unique) and methods and technologies for their solution on computers of various classes. At the same time, there is a transition from the amount of processed data to quality, which requires the concept of developing a new generation of mathematical techniques and software. An important task is to create an active base of mathematical knowledge to ensure the automation or optimization of algorithm construction and their mapping to supercomputer architecture. A prototype of such a base is the project ALGOWIKI developed in the framework of Wikipedia technologies under the guidance of J. Dongarra and Vl.V. Voevodin. This task is within the realm of artificial intelligence and machine learning which, along with big data technologies, forms the foundation of modern modeling. The achieved scales of the triad problems–methods–computers lead to the fact that the integrated computing environment for solving SLAEs should become the form and content of a hierarchical infrastructure that constitutes the industrial-type instrumental environment and implements further stages of the development of high-tech computing and information technologies, the outlines of which are outlined in [1, 24, 93]. To prevent deep specialization from leading to the separation of computer theorists, programmers, end users, their joint efforts should be aimed at creating an intelligent ecosystem that supports interprofessional and human-machine interfaces both to intensify fundamental research and to quickly implement their innovations.
REFERENCES
V. P. Il’in, Mathematical Modeling. Part I: Continuous and Discrete Models (SBRAS, Novosibirsk, 2017).
O. Axelsson, Iterative Solution Methods (Cambridge Univ. Press, Cambridge, 1994).
H. C. Elman, D. J. Silvester, and A. J. Wathen, Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics. Numerical Mathematics and Scientific Computation, 2nd ed. (Oxford Univ. Press, Oxford, 2014).
G. I. Marchuk and Yu. A. Kuznetsov, Iterative Methods and Quadratic Functionals (CC SBRAS, Novosibirsk, 1972) [in Russian].
Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed. (SIAM, 2003).
H. A. Van der Vorst, Iterative Krylov Methods for Large Linear Systems (Cambridge Univ. Press, Cambridge, 2003).
M. A. Olshanskii and E. E. Tyrtyshnikov, Iterative Methods for Linear Systems Theory and Applications (SIAM, Philadelphia, 2014).
J. Liesen and Z. Strakos, Krylov Subspace Methods, Principles and Analysis (Oxford Univ. Press, Oxford, 2013).
V. P. Il’in, Finite Element Methods and Technologies (ICM&MG SBRAS, Novosibirsk, 2007) [in Russian].
V. P. Il’in, Iterative Incomplete Factorization Methods. (World Science, Singapore, 1992).
H. Fang and Y. Saad, “Two classes of multisecant methods for nonlinear acceleration,” Numer. Linear Algebra Appl. 16 (3), 197–221 (2009).
P. P. Pratara and J. E. Suryanarayana, “Anderson acceleration of the Jacobi iterative method. An efficient alternative to Krylov methods for large, sparse linear systems,” J. Comput. Phys. 306, 43–54 (2016).
H. F. Walkert and P. Ni, “Anderson acceleration for fixed-point iterations,” SIAM J. Assoc. Comput. Math. 49, 1715–1735 (2011).
V. P. Il’in, “Iterative processes in the Krylov–Sonneveld subspaces,” J. Math. Sci. 24, 890–899 (2017).
D. S. Butyugin, Y. I. Gurieva, V. P. Il’in, and D. V. Perevozkin, “Some geometric and algebraic aspects of domain decomposition methods,” Lect. Notes Comput. Sci. Eng. 104, 117–126 (2016).
Domain Decomposition Methods. http://ddm.org.
V. P. Il’in, “Multi-preconditioned domain decomposition methods in the Krylov subspaces,” Lect. Notes Comput. Sci. 10187, 95–106 (2017).
V. P. Il’in, “Problems of parallel solution of large systems of linear algebraic equations,” J. Math. Sci. 216, 795–804 (2016).
A. Toselli and O. Widlund, Domain Decomposition Methods: Algorithms and Theory (Springer, Berlin, 2005).
P. N. Vabishchevich, “Incomplete iterative implicit schemes.” Comput. Meth. Appl. Math. 2019.
V. P. Il’in, “High-performance computation of initial boundary value problems,”: PCT 2018, CCIS 910, ed. by L. Sokolinsky and M. Zymbler (Springer, 2018), pp. 186–199.
J. Dongarra, List of freely available software for linear algebra on the web (2006). http://netlib.org/utk/people/JackDongarra/la-sw.html.
R. Barret, M. Bery, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. A. van der Vorst, Templates for the Solution of Linear Systems. Building Blocks for Iterative Methods (SIAM, Philadelphia, 1994).
V. P. Il’in, “On an integrated computational environment for numerical algebra,” PCT 2019, CCIS 1063, ed. by L. Sokolinsky and M. Zymbler (Springer, 2019), pp. 91–106.
M. Arioli, “Generalized Golub–Kahan diagonalization and stopping criteria,” SIAM J. Matrix Anal. Appl. 34 (2), 57–92 (2013).
N. J. Higham. Accuracy and Stability of Numerical Algorithms (SIAM, Philadelphia, 2002).
V. P. Il’in, Finite Difference and Finite Volume Methods for Elliptic Equations (Inst. Vychisl. Mat. Mat. Geofiz., Ross. Akad. Nauk, Novosibirsk, 2001) [in Russian].
K. M. Soodhalter, E. Sturler, and M. Kilmer, “A survey of subspace recycling iterative methods.” https://arxiv.org/abs/2001.10347.
S.-C. T. Choi, C. C. Paige, and M. A. Saunders, “INRES-QLP: A Krylov subspace method for indefinite or singular symmetric systems,” SIAM J. Sci. Comput. (2015). arXiv:1003.4042 [math.NA].
I. E. Kaporin, “New convergence results and preconditioning strategies for the conjugate gradient method,” J. Numer. Linear Algebra Appl. 1, 179–210 (1994).
I. E. Kaporin, “High quality preconditioning of a general symmetric positive definite matrix based on its U T U+U T R+R T U-Decomposition,” J. Numer. Linear Algebra Appl. 5, 483–509 (1998).
I. E. Kaporin and I. N. Konshin, “A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems,” J. Numer. Linear Algebra Appl. 9, 141–162 (2002).
V. P. Il’in, “Methods of semiconjugate directions,” Russ. J. Numer. Anal. Math. Model. 23, 369–387 (2008).
V. P. Il’in, “Two-level least squares methods in Krylov subspaces,” J. Math. Sci. 232, 892–901 (2019).
L. A. Knizhnerman, “Error bounds for the Arnoldi method: A set of extreme eigenpairs,” J. Numer. Linear Algebra Appl. 296, 191–211 (1999).
V. P. Il’in, “Biconjugate direction methods in Krylov subspaces,” J. Appl. Indust. Math. 4 (1), 65–78 (2010).
M. P. Neuenhofen and C. Greif, “MSTAB: stabilized inducted dimension reduction for KRYLOV subspace recycling,” SIAM J. Sci. Comput. 40, 554–571 (2018).
M. A. Saunders, H. D. Simon, and E. L. Yip, “Two conjugate-gradient-type methods for unsymmetric linear equations,” SIAM J. Numer. Anal. 25, 927–940 (1988).
R. Estrin and C. Greif, “SPMR: a family of saddle-point minimum residual solvers,” SIAM J. Sci. Comput. 40, 1884–1914 (2018).
Y. Notay, “Flexible conjugate gradients,” SIAM J. Sci. Comput. 22, 1444–1460 (2000).
A. M. Bradley, Algorithms of the equilibration of matrices and their application to limited-memory quasi-Newton methods, PhD thesis (ICME, Stanford Univ., 2010).
O. E. Livne and G. H. Golub, “Scaling by binormalization,” J. Numer. Algorithms 35, 97–120 (2004).
V. P. Il’in and R. Kellog, “Analysis of flow directed iterations,” J. Comp. Math. 10 (1), 1–18 (1992).
D. N. Arnold, R. S. Faik, and R. Winther, “Preconditioning in H(div) and applications,” J. Math. Comput. 66, 937–984 (1997).
M. Benzi, “Preconditioning techniques for large linear systems: A survey,” J. Comput. Phys. 82, 418–477 (2002).
N. J. Higham and T. Mary, “A new preconditioner that exploits low-rank approximations for factorization error,” SIAM J. Sci. Comput. 41, 59–82 (2019).
R. Hiptmair, “Operator preconditioning,” J. Comput. Math. Appl. 52, 699–706 (2006).
K. Mardal and R. Winther, “Preconditioning discretizations of systems of partial differential equations,” J. Numer. Linear Algebra Appl. 18, 1–40 (2011).
P. S. Vassilevski, Multi-Level Block Factorization Preconditioners (Springer, New York, 2008).
A. Wathen, “Preconditioning,” Acta Numer., No. 24, 329–376 (2015).
R. Bridson and C. Greif, “A multipreconditioned conjugate gradient algorithm,” SIAM J. Matrix Anal. Appl. 27, 1056–1068 (2006).
V. Dolean, P. Jolivet, and F. Nataf, An Introduction to Domain Decomposition Methods: Algorithms, Theory and Parallel Implementation (SIAM, Philadelphia, 2015).
Y. L. Gurieva and V. P. Il’in, “On coarse grid correction methods in the Krylov subspaces,” J. Math. Sci. 232, 74–82 (2018).
Y. M. Laevsky and A. M. Matsokin, “Decomposition methods for solving elliptic and parabolic boundary value problems,” Sib. Zh. Ind. Mat. 2, 361–372 (1999).
Y. Vassilevski, “A hybrid domain decomposition method based on aggregation,” Numer. Linear Algebra Appl. 11, 327–341 (2004).
Y. Vassilevski and M. A. Olshanskii, Short Course on Multi-Grid and Domain Decomposition Methods (MAKS, Moscow, 2007).
L. Yu. H. Xiang and F. Nataf, “Two-level algebraic domain decomposition preconditioners using Jacobi–Schwarz smoother and adaptive coarse grid corrections,” J. Comput. Appl. Math. 261, 1–13 (2014).
A. Gaul, M. H. Gutknecht, J. Hesenta, and R. Nabben, “A framework for deflated and augmented Krylov subspace methods,” SIAM J. Matrix Anal. Appl. 34, 495–518 (2013).
R. Nabben and C. Vuik, “A comparison of deflation and coarse grid correction applied to porous media flow,” SIAM J. Numer. Anal. 42, 631–647 (2004).
R. Bank, R. Falgout, T. Jones, T. Manteuffel, S. McCormick, J. Ruge, “Algebraic multigrid domain and range decomposition (AMG-DD/AMG-RD),” SIAM J. Sci. Comput. 37, 113–136 (2015).
A. Brandt, “Algebraic multigrid theory: The symmetric case,” J. Appl. Math. Comput., No. 19, 23–56 (1986).
V. V. Shaidurov, “Some estimates of the rate of convergence for the cascadic conjugate-gradient method,” J. Comput. Math. Appl. 31 (4–5), 161–171 (1996).
Y. L. Gurieva, V. P. Il’in, and A. V. Petukhov, “On multigrid methods for solving two-dimensional boundary-value problems,” J. Math. Sci. 249 (2), 118–127 (2020).
Y. Notay, “Algebraic multigrid for Stokes equations,” SIAM J. Sci. Comput. 39, 88–111 (2017).
Y. Notay and A. A. Napov, “An efficient multigrid method for graph Laplacian systems II: robust aggregation,” SIAM J. Sci. Comput. 39, 379–403 (2017).
M. A. Olshanskii, Lecture Notes on Multigrid Methods (Inst. Vychisl. Mat., Ross. Akad. Nauk, Moscow, 2012).
J. M. Tang, R. Nabben, C. Vuik, and Y. A. Erlangga, “Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods,” J. Sci. Comput., No. 39, 340–370 (2009).
R. S. Varga, Iterative Analysis (Springer, 1962).
L. Yu. Kolotilina, “The convergence of certain incomplete block factorization splittings,” J. Math. Sci. 86, 2828–2834 (1997).
A. Yu. Yeremin, L. Yu. Kolotilina, and A. A. Nikishin, “Factorized sparse approximate inverse preconditioning III. Iterative construction of preconditioners,” J. Math. Sci. 101, 3237–3254 (2000).
P. Kumar, L. Grigori, F. Nataf, and Q. Nui, “On relaxed nested factorization and combination preconditioning,” Int. J. Comput. Math. 93 (1), 178–199 (2016).
P. S. Vassilevski, “Preconditioning mixed finite element saddle-point elliptic problems,” J. Numer. Linear Algebra Appl. 3 (1), 1–20 (1996).
W. Hackbusch, Hierarchische Matrizen: Algorithmen und Analysis (Springer, Berlin, 2009).
S. A. Solovyev, “Multifrontal hierarchically solver for 3D discretized elliptic equations” in FDM 2014, Ed. by I. Dimov, I. Faragi, L. Vulkov, LNCS (Springer, Cham, 2015), vol. 9045, pp. 371–378.
M. Arioli and M. Manzini, “A network programming approach in solving Darcy‘s equations by mixed finite elements methods,” Electron. Trans. Numer. Anal. 22, 41–70 (2006).
M. Bern, J. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo, “Support-graph preconditioners,” SIAM J. Matrix Anal. Appl. 27, 930–951 (2006).
C. Ponce and P.S. Vassilevski, “Solving graph Laplacian systems through recursive partitioning and two-grid preconditioning,” SIAM J. Matrix Anal. Appl. 38, 621–648 (2017).
V. P. Il’in and K. Yu. Laevsky, “Generalized compensation principle in incomplete factorization methods,” Russ. J. Numer. Anal. Math. Model. 12, 399–412 (1997).
M. Heath and C. Romine, “Parallel solution of triangular systems on distributed-memory multiprocessors,” SIAM J. Sci. Stat. Comp. 9, 558–588 (1988).
E. Hutter and E. Solomonik, “Communication-avoiding Cholesky QR-2 for rectangular matrices,” arXiv: 1710.08471v6.
A. Ruhe, “Rational Krylov sequence methods for eigenvalue computation,” J. Linear Algebra Appl. 58, 39–45 (1984).
N. N. Kuznetsova, O. V. Diyankov, S. V. Kotegov, I. V. Krasnogorov, V. Y. Pravilnikov, and S. Y. Maliassov, “The family of nested factorizations,” Russ. J. Numer. Anal. Math. Model. 22, 393–412 (2007).
R. Wang, Q. Nu, and L. Lu, “A twisted block tangential filtering decomposition preconditioner,” Math. Prob. Eng. Article ID 282307 (2009).
M. Benzi, G. H. Golub, and J. Liesen, “Numerical solution of saddle point problems,” Acta Numerica 14, 1–137 (2005).
F. Brezzi, Stability of Saddle Points in Finite Dimensions, Frontiers in Numerical Analysis (Springer, Berlin, 2013), pp. 17–61.
Y. Notay and A. Napov, “Further comparison of additive and multiplicative coarse grid correction,” J. Appl. Numer. Math. 65, 53–62 (2013).
Y. V. Bychenkov and E. V. Chizhonkov, Iterative Methods for Solving Saddle Point Problems (Binom, Moscow, 2010) [in Russian].
C. Greif and D. Schotzau, “Preconditioners for saddle point linear systems with highly singular (1.1) Blocks,” in Special Volume on Saddle Point Problems, Electron. Trans. J. Numeг. Anal. 22, 114–121 (2006).
C. Greif and D. Schotzau, “Preconditioners for the discretized harmonic Maxwell equations in mixed form,” Numer. Linear Algebra Appl. 14, 281–287 (2007).
Y. Notay, “Convergence of some iterative methods for symmetric saddle point linear systems,” SIAM J. Matrix Anal. Appl. 40, 122–146 (2019).
V. P. Il’in and G. Y. Kazantsev, “Iterative solution of saddle-point systems of linear equations,” J. Math. Sci. 249, 199–208 (2020).
Y. Notay, “Algebraic two-level convergence theory for singular systems,” SIAM J. Matrix Anal. Appl. 37, 1419–1439 (2016).
J. Dongarra, L. Grigori, and N. J. Higham, “Numerical algorithms for high performance computational science,” Phil. Trans. R. Soc. A 378, (2020).
V. P. Il’in, “Projection methods in Krylov subspaces,” J. Math. Sci. 240, 772–782 (2019).
N. I. Gorbenko and V. P. Il’in, “The additive Peaceman–Rachford method,” J. Math. Sci. 216, 753–760 (2016).
A. Y. Aleinikov, R. A. Barabanov, Y. G. Bartenev, et al., “An application of parallel solvers for SLAEs in the applied packages for engineering,” Proc. Int. Conf. “Supercomputing and Mathematical Modeling,” (Unicef, 2015), pp. 102–110.
P. Bastian and M. Blatt, Iterative solver template library (DUNE). https://www.dune-project.org/.
Y. V. Vassilevskii, I. N. Kon’shin, G. V. Kopytov, and K. M. Terekhov, INMOST—A Software Platform and Graphical Medium for the Development of Parallel Numerical Models on General-Type Grids (Moscow State Univ., Moscow, 2018) [in Russian].
ACKNOWLEDGMENTS
I am grateful to two anonymous reviewers whose remarks helped improve the presentation.
Funding
This work was supported by the Russian Foundation for Basic Research, project no. 19-11-50073 within the competition of review articles “Expansion” and by the Ministry for Science and Higher Education, project no. 2020-0012.
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated by A. Klimontovich
Rights and permissions
About this article
Cite this article
Il’in, V.P. Iterative Preconditioned Methods in Krylov Spaces: Trends of the 21st Century. Comput. Math. and Math. Phys. 61, 1750–1775 (2021). https://doi.org/10.1134/S0965542521110099
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0965542521110099