Page 444 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 444
MATRIX COMPUTATIONS AND NUMERICAL (MS-47)
of the original differential system. In addition, we will show that such tridiagonalization is
always feasible with piecewise-smooth functions and will completely characterize algorithmic
breakdowns. We will then discuss numerical implementations of the Lanczos-like procedure
and present its extensions to systems of linear and non-linear partial differential equations.
Parallel Newton-Chebyshev Polynomial Preconditioners for the
Conjugate Gradient method
Ángeles Martínez, amartinez@units.it
Department of Mathematics and Earth Sciences, University of Trieste, Italy
Coauthor: Luca Bergamaschi
Discretization of PDEs modeling different processes and constrained/unconstrained optimiza-
tion problems often require the repeated solution of large and sparse linear systems Ax = b.
The size of these system can be of order 106 ÷ 109 and this calls for the use of iterative methods,
equipped with ad-hoc preconditioners as accelerators running on a parallel computing environ-
ment. In most cases, the huge size of the matrices involved prevents their complete storage. In
these instances only the application of the matrix to a vector is available as a routine (matrix
-free regime). Differently from direct factorization methods, iterative methods do not need the
explicit knowledge of the coefficient matrix. The issue is the construction of a preconditioner
which also work in a matrix-free regime. Polynomial preconditioners, i.e. preconditioners that
can be expressed as Pk(A), are very attractive for several reasons i.e. their construction is only
theoretical, namely only the coefficients of the polynomial are to be computed with negligible
computational cost, the application of Pk(A) requires a number, k, of matrix-vector products
so that they can be implemented in a matrix-free regime, and the eigenvectors of the precondi-
tioned matrix are the same as those of A.
We consider polynomial preconditioners to accelerate the Conjugate Gradient method in the
solution of large symmetric positive definite linear systems in massively parallel environments.
We put in connection a specialized Newton method to solve the matrix equation X−1 = A [1]
and the Chebyshev polynomials for preconditioning. We propose a simple strategy to avoid
clustering of the extremal eigenvalues in order to speed-up convergence. Numerical results
on very large linear systems (up to 8 billion unknowns) in a parallel environment show the
efficiency of the proposed class of preconditioners.
References
[1] L. BERGAMASCHI AND A. MARTÍNEZ, Parallel Newton-Chebyshev polynomial precon-
ditioners for the Conjugate Gradient method, Computational and Mathematical Methods,
(2021). to appear.
442
of the original differential system. In addition, we will show that such tridiagonalization is
always feasible with piecewise-smooth functions and will completely characterize algorithmic
breakdowns. We will then discuss numerical implementations of the Lanczos-like procedure
and present its extensions to systems of linear and non-linear partial differential equations.
Parallel Newton-Chebyshev Polynomial Preconditioners for the
Conjugate Gradient method
Ángeles Martínez, amartinez@units.it
Department of Mathematics and Earth Sciences, University of Trieste, Italy
Coauthor: Luca Bergamaschi
Discretization of PDEs modeling different processes and constrained/unconstrained optimiza-
tion problems often require the repeated solution of large and sparse linear systems Ax = b.
The size of these system can be of order 106 ÷ 109 and this calls for the use of iterative methods,
equipped with ad-hoc preconditioners as accelerators running on a parallel computing environ-
ment. In most cases, the huge size of the matrices involved prevents their complete storage. In
these instances only the application of the matrix to a vector is available as a routine (matrix
-free regime). Differently from direct factorization methods, iterative methods do not need the
explicit knowledge of the coefficient matrix. The issue is the construction of a preconditioner
which also work in a matrix-free regime. Polynomial preconditioners, i.e. preconditioners that
can be expressed as Pk(A), are very attractive for several reasons i.e. their construction is only
theoretical, namely only the coefficients of the polynomial are to be computed with negligible
computational cost, the application of Pk(A) requires a number, k, of matrix-vector products
so that they can be implemented in a matrix-free regime, and the eigenvectors of the precondi-
tioned matrix are the same as those of A.
We consider polynomial preconditioners to accelerate the Conjugate Gradient method in the
solution of large symmetric positive definite linear systems in massively parallel environments.
We put in connection a specialized Newton method to solve the matrix equation X−1 = A [1]
and the Chebyshev polynomials for preconditioning. We propose a simple strategy to avoid
clustering of the extremal eigenvalues in order to speed-up convergence. Numerical results
on very large linear systems (up to 8 billion unknowns) in a parallel environment show the
efficiency of the proposed class of preconditioners.
References
[1] L. BERGAMASCHI AND A. MARTÍNEZ, Parallel Newton-Chebyshev polynomial precon-
ditioners for the Conjugate Gradient method, Computational and Mathematical Methods,
(2021). to appear.
442
