Chebyshev smoothing with adaptive block-FSAI preconditioners for the multilevel solution of higher-order problems

Pablo Jiménez Recio, Marc Alexander Schweitzer · 2025

Read Chebyshev smoothing with adaptive block-FSAI preconditioners for the multilevel solution of higher-order problems by Pablo Jiménez Recio, Marc Alexander Schweitzer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06744.txt.

Introduction

Smoother steps inside multilevel solvers for stiff formulas are tested by Pablo Jiménez Recio and one co-author in a 2025 numerical analysis paper. The test problems are the biharmonic and triharmonic formulas, split onto grids with the partition of unity method. Multilevel V-cycles need a smoothing pass that damps errors without full solves.

The authors pair Chebyshev passes of the fourth kind with factored sparse near-inverse preconditioners, which stand in cheaply for exact matrix inverses. They add a new adaptive building method that uses the block form these grid splits produce, plus a simpler statement of the Chebyshev pass itself. Results are checked on the multilevel solution of the higher-order problems. Work of this kind matters because near-inverses that adapt to block form can make large, high-order simulations practical.

Catalog record

CREATORPablo Jiménez Recio, Marc Alexander Schweitzer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-06744

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Chebyshev smoothing with adaptive block-FSAI preconditioners for the multilevel solution of higher-order problems Pablo Jiménez Recio, Marc Alexander Schweitzer Abstract In this paper, we assess the performance of adaptive and nested factorized sparse approximate inverses as smoothers in multilevel V-cycles, when smoothing is performed following the Chebyshev iteration of the fourth kind. For our test problems, we rely on the partition of unity method to discretize the biharmonic and triharmonic equations in a multilevel manner. Inspired by existing algorithms, we introduce a new adaptive algorithm for the construction of sparse approximate inverses, based on the block structure of matrices arising in the partition of unity method. Additionally, we also present a new (and arguably simpler) formulation of the Chebyshev iteration of the fourth kind. 1 Introduction The use of the Chebyshev iteration for concatenating smoothing steps in multigrid/multilevel iterations has been redefined by the significant work of Lottes [ 17 ] , which has allowed dispensing with the estimate of the lower end of the fine spectrum of the preconditioned matrix. The new Chebyshev iteration of the fourth kind was quickly adopted in PETSc and the deal.II library [ 3 ] . In this work, we combine this new Chebyshev iteration with underlying Factorized Sparse Approximate Inverse (FSAI) preconditioners, as developed in recent years by Janna et al. [ 13 , 11 , 14 ] , and which have already been used as smoothers in multilevel approaches [ 20 , 12 ] . We will put these preconditioners into practice for a variety of problems generated with the Partition of Unity Method (PUM) of Schweitzer and Griebel [ 23 , 7 ] . The paper is organized as follows. In Section 2 we introduce the block-FSAI preconditioner, where our focus on block matrices follows from the natural block structure of matrices arising from the PUM. We pay special attention to developing our own adaptive algorithm for the construction of a suitable sparsity pattern for PUM block matrices, based on the one from [ 11 ] , and also describe the possibility of nesting FSAI preconditioners. In Section 3 we present the Chebyshev iteration, explain its raison d’être and delve into its use as a way to optimally concatenate smoothing steps in multilevel iterations, paying special attention to the work of Lottes [ 17 ] . Given the simplicity of the new Chebyshev iteration of the fourth kind (which we simplify even further), we choose it for our work instead of the optimized (but more involved) version also introduced by Lottes. In Section 4 we provide a brief description of the PUM, whose discrete function spaces possess a natural geometric multilevel structure, as well as basis functions of any desired regularity. Finally, in Section 5 we present some numerical experiments to attest the effectiveness and efficiency of the (adaptive and nested) block-FSAI preconditioners, which we embed within a Chebyshev iteration. The PUM allows us to test our multilevel solvers on higher-order problems such as the biharmonic and triharmonic equations, which provide a challenging scenario, since the usual Jacobi and Gauss-Seidel iterations are not particularly effective smoothers in this case, or at least not for PUM discretizations. We note that the multilevel solution of the biharmonic equation has already been investigated by other authors, see e.g. [ 25 ] and the references therein. 2 The FSAI preconditioner For an invertible matrix A\in\mathbb{R}^{N\times N} and some predefined sparsity pattern \mathcal{P}\subset\{1,\dots,N\}^{2} , a sparse approximate inverse (SAI) of A based on \mathcal{P} is some matrix M\in\mathbb{R}^{N\times N} with sparsity pattern \mathcal{P}(M)\coloneqq\{(i,j)\,\colon\,M_{ij}\neq 0\}\subset\mathcal{P} which approximates A^{-1} , usually by solving M\coloneqq\argmin_{\mathcal{P}(\tilde{M})\subset\mathcal{P}}\lVert I-\tilde{M}A\rVert_{F}, with \lVert\cdot\rVert_{F} the Frobenius norm, defined by \lVert B\rVert_{F}^{2}=\trace(B^{\top}B) . This constitutes the basis of the SAI preconditioner [ 24 ] . Note however that, even if the matrix A is symmetric positive definite (s.p.d.), the resulting matrix M will not be s.p.d., and thus the preconditioned matrix will also not be s.p.d. The Factorized Sparse Approximate Inverse (FSAI) preconditioner overcomes this issue, and (following the construction of Janna et al. [ 14 ] ) it does so by constructing a sparse approximation G\approx L^{-1} to the inverse of the (unknown) triangular Cholesky factor L of A=LL^{\top} , leading to M\coloneqq G^{\top}G\approx L^{-\top}L^{-1}=A^{-1} , with the preconditioned matrix being GAG^{\top} . Let us first introduce the notation that we will use for working with block-structured matrices as those arising in the PUM. Definition 2.1 . Let n\in\mathbb{N} and \mathfrak{B}\coloneqq\{m_{i}\}_{i=1}^{n} a set of n positive integers with N=\sum_{i=1}^{n}m_{i} . By saying that a matrix A\in\mathbb{R}^{N\times N} has the block structure \mathfrak{B} , we allow ourselves to interpret it as \displaystyle A \displaystyle=(A_{ij}),\quad i,j\in\{1,\dots,n\}, \displaystyle A_{ij} \displaystyle=(a_{kl})\in\mathbb{R}^{m_{i}\times m_{j}}. We further denote \mathcal{P}(A)\coloneqq\{(i,j)\,\colon\,A_{ij}\neq\mathbb{O}_{m_{i}\times m_{j}}\}\subset\{1,\dots,n\}^{2} the sparsity pattern of such a matrix, and call a matrix block-diagonal if \mathcal{P}(A)\subset\{(i,i)\,\colon\,i\in\{1,\dots,n\}\}. Finally, we denote \diag_{\mathfrak{B}}(A) the block-diagonal component of a matrix A , i.e. the matrix with diagonal blocks A_{ii} and \mathbb{O}_{m_{i}\times m_{j}} off-diagonal blocks. For any block matrix B as in Definition 2.1 and sets of indices \mathcal{I},\mathcal{J}\subset\{1,\dots,n\} , we will denote B[\mathcal{I},\mathcal{J}] the restriction of B to row indices in \mathcal{I} and column indices in \mathcal{J} . We may now define the block-FSAI preconditioner. Definition 2.2 . Let A be a s.p.d. matrix with block structure \mathfrak{B}\coloneqq\{m_{i}\}_{i=1}^{n} as in Definition 2.1 . Let \mathcal{P}\subset\{1,\dots,n\}^{2} be some lower triangular sparsity pattern containing the diagonal, i.e. (i,i)\in\mathcal{P}\quad\forall i\in\{1,\dots,n\},\qquad\text{and}\qquad i\geq j\quad\forall(i,j)\in\mathcal{P}, (1) Let us denote its rows, with and without the corresponding row index, by \mathcal{P}_{i}\coloneqq\{j\,\colon\,(i,j)\in\mathcal{P}\},\quad\tilde{\mathcal{P}}_{i}\coloneqq\mathcal{P}_{i}\setminus\{i\},\qquad i\in\{1,\dots,n\}. We define the block-FSAI matrix for A based on \mathcal{P} as the matrix F with block structure \mathfrak{B} , sparsity pattern \mathcal{P}(F)\subset\mathcal{P} and non-zero block-entries given by F_{ii}=\mathbb{I}_{m_{i}\times m_{i}},\quad F[\{i\},\,\tilde{\mathcal{P}}_{i}]=-A[\{i\},\,\tilde{\mathcal{P}}_{i}]\,A[\tilde{\mathcal{P}}_{i},\tilde{\mathcal{P}}_{i}]^{-1},\qquad i\in\{1,\dots,n\}. (2) The block-FSAI preconditioning matrix for A based on \mathcal{P} is then M\coloneqq F^{\top}S^{-1}F , where S is the block-diagonal matrix (also with block structure \mathfrak{B} ) given by S_{ii}\coloneqq A_{ii}-A[\{i\},\,\tilde{\mathcal{P}}_{i}]A[\tilde{\mathcal{P}}_{i},\tilde{\mathcal{P}}_{i}]^{-1}A[\tilde{\mathcal{P}}_{i},\{i\}],\qquad i\in\{1,\dots,n\}. (3) We may also write M=G^{\top}G for G=S^{-1/2}F , with the preconditioned matrix then being GAG^{\top} . Remark 2.1 . From now on, unless explicitly stated otherwise, every reference to a “lower triangular sparsity pattern” will mean also including the diagonal, i.e. a sparsity pattern fulfilling both conditions in ( 1 ). Lemma 2.1 . Let A be a s.p.d. matrix with block structure \mathfrak{B} and F be defined as in ( 2 ) for some lower triangular sparsity pattern \mathcal{P} . Let S be the block-diagonal matrix with blocks given by ( 3 ). It holds that \diag_{\mathfrak{B}}(FA)=S=\diag_{\mathfrak{B}}(FAF^{\top}), and in particular it follows that the block-diagonal of the block-FSAI preconditioned matrix, \diag_{\mathfrak{B}}(GAG^{\top}) , is the identity matrix. Proof. The first identity follows directly from ( 2 ) and ( 3 ). Indeed, (FA)_{ii}=F[\{i\},\,\mathcal{P}_{i}]\,A[\mathcal{P}_{i},\,\{i\}]=S_{ii},\quad\forall i\in\{1,\dots,n\}. The second one can also be easily checked relying on the first one and writing (FAF^{\top})_{ii}=\begin{pmatrix}I_{ii}&F[\{i\},\,\tilde{\mathcal{P}}_{i}]\end{pmatrix}\begin{pmatrix}A_{ii}&A[\{i\},\,\tilde{\mathcal{P}}_{i}]\\ A[\tilde{\mathcal{P}}_{i},\{i\}]&A[\tilde{\mathcal{P}}_{i},\tilde{\mathcal{P}}_{i}]\end{pmatrix}\begin{pmatrix}I_{ii}\\ F^{\top}[\tilde{\mathcal{P}}_{i},\,\{i\}]\end{pmatrix}=\\ =\begin{pmatrix}I_{ii}&F[\{i\},\,\tilde{\mathcal{P}}_{i}]\end{pmatrix}\begin{pmatrix}S_{ii}\\ 0\end{pmatrix}=S_{ii}. The final statement follows trivially for G=S^{-1/2}F . ∎ Remark 2.2 . For the simplest choice of a diagonal sparsity pattern \mathcal{P}=\{(i,i)\,\colon\,i\in\{1,\dots,n\}\}, the resulting matrix F is the identity matrix and S=\diag_{\mathfrak{B}}(A) , so the block-FSAI preconditioner reduces to a block-Jacobi preconditioner. Let us now introduce an important concept which, as we will show, is deeply connected to the FSAI preconditioner. Definition 2.3 . For a s.p.d. matrix B\in\mathbb{R}^{N\times N} , the Kaporin number is

Read the complete text