Generalized Chebyshev Acceleration

Nurgül Gökgöz · 2025

Read Generalized Chebyshev Acceleration by Nurgül Gökgöz (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-2504-18465.txt.

Introduction

Nurgül Gökgöz presents a 2025 arXiv paper on speeding up simple iterative solvers for linear systems. Semi-iterative acceleration leans on Chebyshev polynomials, and Gökgöz swaps in their generalized cousins tied to the A2 root system. Applied as a wrapper around the plain Jacobi method, the scheme squeezes far more progress from each pass. An example works through the gains. The method carries stated restrictions on when it applies. The author offers it as a fresh acceleration engine for slow solvers.

Catalog record

CREATORNurgül Gökgöz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-18465

Browse the full library · About the Tower of Babel

Full text

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

Generalized Chebyshev Acceleration Nurgül Gökgöz Abstract . We use generalized Chebyshev polynomials, associated with the root system A 2 A_{2} , to provide a new semi-iterative method for accelerating simple iterative methods for solving linear systems. We apply this semi-iterative method to the Jacobi method, and give an example. There are certain restrictions but the resulting acceleration is rather high. 2010 Mathematics Subject Classification 65F10 Let A be an n\times n invertible matrix with real entries. Consider the linear system A\mathbf{x}=\mathbf{b} . For a general matrix with reasonable size and entries, we normally use some direct method of solution, such as Gaussian elimination. However, for larger matrices, we may prefer to use an iterative method. Iterative methods can be useful for linear problems involving many variables, where direct methods are computationally expensive, if not impossible. See [ Gr97 ] , and [ Va09 ] , for several iterative algorithms. The Chebyshev semi-iterative method is an enhancement of simple iterative methods for solving linear systems. It improves convergence by utilizing Chebyshev polynomials to optimize the choice of iteration parameters, thereby accelerating convergence compared to standard stationary iterative methods. The method requires an estimate of the smallest and largest eigenvalues of the iteration matrix to construct the Chebyshev polynomial sequence [ FP72 ] , [ Va09 ] . In this paper, we use generalized Chebyshev polynomials associated with the root system A_{2} , see [ Mu06 ] , and provide a new approach for accelerating convergence. We apply this new approach to the Jacobi method. Even though, there are certain restrictions, the resulting acceleration is rather high The organization of the paper is as follows. In the first section, we summarize the basics of semi-iterative methods, and fix some notation that will be used in the rest of the paper. In the second section, we outline the classical Chebyshev acceleration method to make its generalization more accessible. In the third section, we provide certain properties of generalized Chebyshev polynomials associated with the root system A_{2} . In the last section, we present our main result for accelerating the convergence of simple iterative methods by using the generalized Chebyshev polynomials. 1. Semi-Iterative Methods An iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions. This general approach can be used to study the solution of the linear systems A\mathbf{x}=\mathbf{b} . For a comprehensive treatment of the subject, one can see [ Gr97 ] , and [ Va09 ] . In this section, we summarize the basics of semi-iterative methods, and fix some notation that will be used in the rest of the paper. We will mostly follow the exposition of [ Va09 ] . Before we can explain semi-iterative methods, we first need an iterative method. For simplicity, we consider the Jacobi method. Given a system A\mathbf{x}=\mathbf{b} , with nonzero diagonal, we set A=L+D+U where L and U are respectively strictly lower and upper triangular matrices, and D is the diagonal matrix. Consider M=-D^{-1}(L+U) and \mathbf{g}=D^{-1}\mathbf{b} . The Jacobi method uses the following iterative process \mathbf{x}^{(m)}=M\mathbf{x}^{(m-1)}+\mathbf{g},\quad m\geq 1. (1.1) To investigate the convergence, we observe that the required solution of the system A\mathbf{x}=\mathbf{b} shall satisfy \mathbf{x}=M\mathbf{x}+\mathbf{g}. (1.2) We define the error vector as \epsilon^{(m)}:=\mathbf{x}-\mathbf{x}^{(m)} . Combining ( 1.1 ) and ( 1.2 ), we see that the error vector has the following property \epsilon^{(m)}=M\epsilon^{(m-1)}=\ldots=M^{m}\epsilon^{(0)}. (1.3) The error vector converges to zero if and only if all the eigenvalues M have absolute values less than one, i.e. the spectral radius \rho(M) is less than one. This is easily proved in the generic case. Suppose that \lambda_{1},\ldots\lambda_{n} are eigenvalues and \{\mathbf{v}_{1},\ldots\mathbf{v}_{n}\} is a full set of independent eigenvectors of M , respectively. We have \epsilon^{(0)}=\sum_{j=1}^{n}\alpha_{j}\mathbf{v}_{j},\quad\epsilon^{(m)}=M^{m}\epsilon^{(0)}=\sum_{j=1}^{n}\alpha_{j}\lambda_{j}^{m}\mathbf{v}_{j}. (1.4) The coefficients \alpha_{j} depend on the initial guess \mathbf{x}^{(0)} , and therefore they are random. However, the convergence is not related with these coefficients. More precisely, we have M^{m}\epsilon^{(0)}\rightarrow 0 if and only if |\lambda_{j}|<1 for all j . If the absolute value of an eigenvalue, say \lambda_{1} , is greater than the absolute values of all other eigenvalues, then the dominant term in M^{m}\epsilon^{(0)} is \alpha_{1}\lambda_{1}^{m}\mathbf{v}_{1} . The rate of convergence ultimately depends on the size of |\lambda_{1}| , and therefore the spectral radius. We may obtain a faster rate of convergence by weighting the components of the error vector, see ( 1.4 ), suitably. Consider the following linear combination \mathbf{y}^{(m)}:=\sum_{j=0}^{m}\nu_{j}(m)\mathbf{x}^{(j)},\quad m\geq 0. (1.5) This is called a semi-iterative method with respect to the iterative method of ( 1.1 ). We want this new iteration to converge to the same solution, so there is an obvious restriction on the coefficients \nu_{j}(m) . If the first guess for the original iteration is correct, i.e. \mathbf{x}^{(0)}=\mathbf{x} , then \mathbf{x}^{(1)}=\mathbf{x}^{(2)}=\ldots=\mathbf{x} , as well. Since we want \mathbf{y}^{(m)} to converge to \mathbf{x} , we must have \sum_{j=0}^{m}\nu_{j}(m)=1. (1.6) We shall relate the error of the former iterative process with the error of this new setup. For this purpose, we introduce a new notation, and define the error vector \eta^{(m)}:=\mathbf{x}-\mathbf{y}^{(m)} in the semi-iterative case. Using ( 1.5 ), and ( 1.6 ), we obtain \eta^{(m)}=\mathbf{x}-\sum_{j=0}^{m}\nu_{j}(m)\mathbf{x}^{(j)}=\sum_{j=0}^{m}\nu_{j}(m)(\mathbf{x}-\mathbf{x}^{(j)}). Recalling \epsilon^{(j)}=\mathbf{x}-\mathbf{x}^{(j)} , and applying ( 1.3 ), we get \eta^{(m)}=\sum_{j=0}^{m}\nu_{j}(m)M^{j}\epsilon^{(0)}. It is now apparent that \eta^{(m)} can be obtained by applying a suitable polynomial of M to the initial error vector \epsilon^{(0)} of the iterative method of ( 1.1 ). We define p_{m}(\lambda):=\sum_{j=0}^{m}\nu_{j}(m)\lambda^{j}. Using the setting as in ( 1.4 ), we easily see that \eta^{(m)}=\sum_{j=1}^{n}\alpha_{j}p_{m}(\lambda_{j})\mathbf{v}_{j}=p_{m}(M)\epsilon^{(0)}. (1.7) With standard definitions of vector and matrix norms, see [ Va09 ] , it follows that \lVert\eta^{(m)}\rVert=\lVert p_{m}(M)\epsilon^{(0)}\rVert\leq\lVert p_{m}(M)\rVert\cdot\lVert\epsilon^{(0)}\rVert,\quad m\geq 0. If we can make the quantities \lVert p_{m}(M)\rVert smaller, compared to \lVert M^{m}\rVert , then the bounds for \lVert\eta^{(m)}\rVert for the semi-iterative method are proportionally smaller, compared to \lVert\epsilon^{(m)}\rVert . 2. Chebyshev Acceleration In this section, we give a short summary of the Chebyshev semi-iterative method with respect to ( 1.1 ) following [ Va09 ] . In the following sections, we will generalize this construction to the generalized Chebyshev polynomials associated with the root system A_{2} . Suppose that M has real eigenvalues with absolute values strictly less than one. Suppose also that we know the spectral radius 0<\rho=\rho(M)<1 . By the definition of Chebyshev semi-iterative method, we choose p_{m}(\lambda)=\frac{C_{m}(\lambda/\rho)}{C_{m}(1/\rho)}. (2.1) where C_{m} is the m th Chebyshev polynomial. We obviously have p_{m}(1)=1 . In other words the restriction ( 1.6 ) is satisfied. The Chebyshev polynomials C_{m} are uniquely defined by the following functional equation C_{m}(\cos(\theta))=\cos(m\theta). The first few Chebyshev polynomials are C_{0}(t)=1 , C_{1}(t)=t , C_{2}(t)=2t^{2}-1 , and they satisfy the recurrence relation C_{m}(t)=2tC_{m-1}(t)-C_{m-2}(t),\quad m\geq 2. This relation, applied to C_{m}(\lambda/\rho)=C_{m}(1/\rho)p_{m}(\lambda) , gives us p_{m}(\lambda)C_{m}(1/\rho)=2\frac{\lambda}{\rho}C_{m-1}(1/\rho)p_{m-1}(\lambda)-C_{m-2}(1/\rho)p_{m-2}(\lambda),\quad m\geq 2. We observe that p_{m}(\lambda)=\frac{2\lambda C_{m-1}(1/\rho)}{C_{m}(1/\rho)}p_{m-1}(\lambda)-\frac{C_{m-2}(1/\rho)}{C_{m}(1/\rho)}p_{m-2}(\lambda),\quad m\geq 2. We now plug in M for \lambda , and postmultiply throughout by \epsilon^{(0)} . Using the relation with the error vector, see ( 1.7 ), we obtain \eta^{(m)}=\frac{2C_{m-1}(1/\rho)}{C_{m}(1/\rho)}M\eta^{(m-1)}-\frac{C_{m-2}(1/\rho)}{C_{m}(1/\rho)}\eta^{(m-2)},\quad m\geq 2. Recall that \eta^{(j)}=\mathbf{x}-\mathbf{y}^{(j)} for each j , and M\mathbf{x}+\mathbf{g}=\mathbf{x} . Thus, we obtain a new iterative process, \mathbf{y}^{(m)}=\frac{2C_{m-1}(1/\rho)}{\rho C_{m}(1/\rho)}(M\mathbf{y}^{(m-1)}+\mathbf{g})-\frac{C_{m-2}(1/\rho)}{C_{m}(1/\rho)}\mathbf{y}^{(m-2)}. (2.2) For simplicity, we can choose \mathbf{y}^{(0)}=\mathbf{x}^{(0)} , and \mathbf{y}^{(1)}=\mathbf{x}^{(1)} . This is of a similar form to the original iteration, see ( 1.1 ), but involves two earlier vectors instead of one. We

Read the complete text