Advanced
ESOR METHOD WITH DIAGONAL PRECONDITIONERS FOR SPD LINEAR SYSTEMS†
ESOR METHOD WITH DIAGONAL PRECONDITIONERS FOR SPD LINEAR SYSTEMS†
Journal of Applied Mathematics & Informatics. 2015. Jan, 33(1_2): 111-118
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : May 17, 2014
  • Accepted : September 20, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
SEYOUNG OH
JAE HEON YUN
KYOUM SUN KIM

Abstract
In this paper, we propose an extended SOR (ESOR) method with diagonal preconditioners for solving symmetric positive definite linear systems, and then we provide convergence results of the ESOR method. Lastly, we provide numerical experiments to evaluate the performance of the ESOR method with diagonal preconditioners. AMS Mathematics Subject Classification : 65F10.
Keywords
1. Introduction
In this paper, we consider an iterative method for solving the following linear system
PPT Slide
Lager Image
where A = ( aij ) ∈ ℝ n × n is a symmetric positive definite (SPD) matrix. The basic iterative method [6 , 7] for solving the linear system (1) can be expressed as
PPT Slide
Lager Image
where x 0 is an initial vector and A = M N is a splitting of A . To improve the convergence rate of the basic iterative method, the original linear system (1) is usually transformed into the following preconditioned linear system
PPT Slide
Lager Image
where P is called a preconditioner. Then the preconditioned iterative method [1 , 2 , 3 , 5 , 8] for solving the linear system (3) is
PPT Slide
Lager Image
where x 0 is an initial vector and PA = Mp Np is a splitting of PA . It is well known that the necessary and sufficient condition for the iterative method (4) to converge for any x 0 is
PPT Slide
Lager Image
(see [6 , 7] ).
Throughout the paper, we assume that A = D L U , where D = diag( A ) is the diagonal matrix, and L and U are strictly lower triangular and strictly upper triangular matrices, respectively. For a vector x ∈ ℝ n , ∥ x 2 denotes 2 -norm of x and x denotes the conjugate transpose of x . For a square matrix B , ρ ( B ) denotes the spectral radius of B .
In this paper, we only consider diagonal preconditioners P which are diagonal matrices. Recently, Tarazaga and Cuellar [4] proposed two diagonal preconditioners which were obtained by minimizing the norm of the iteration matrix using the Frobenius norm and the infinity norm. The diagonal preconditioner PF obtained by minimizing the Frobenius norm is given by
PPT Slide
Lager Image
where ai stands for the i th row of the matrix A . The diagonal preconditioner PI obtained by minimizing the infinity norm is given by PI = αI , where
PPT Slide
Lager Image
and I denotes the identity matrix of order n . It was shown in [4] that ρ ( I PFA ) < 1 and ρ ( I PIA ) < 1 when A is a strictly diagonal dominant matrix with positive diagonal elements.
We now propose an extended SOR (ESOR) method with diagonal preconditioner P for solving the preconditioned linear system (3), which is defined by
PPT Slide
Lager Image
where ω > 0 is a relaxation parameter. If we rearrange the equation (6), then the ESOR method can be rewritten as
PPT Slide
Lager Image
where HP = I ω ( P −1 ωL ) −1 A and BP = ω ( P −1 ωL ) −1 . The HP is called the iteration matrix for the ESOR method with diagonal preconditioner P . It is easy to see that the ESOR method reduces to the SOR method if P = D −1 . In this respect, the ESOR method can be viewed as an extension of the SOR method.
This paper is organized as follows. In Section 2, we provide convergence results of the ESOR method with diagonal preconditioners including the PF and PI proposed in [4] . In Section 3, we provide numerical experiments to evaluate the performance of the ESOR method with diagonal preconditioners. Lastly, some conclusions are drawn.
2. Convergence results of the ESOR method
In this section, we consider convergence of the ESOR method with diagonal preconditioner for solving the preconditioned linear system (3).
Theorem 2.1. Let A = ( aij ) = D L U be a symmetric positive definite matrix and P = ( pij ) be a diagonal matrix with positive diagonal elements. If
PPT Slide
Lager Image
then the ESOR method with the diagonal preconditioner P converges for any x 0 .
Proof . Notice that aii > 0 for all i , U = LT and
PPT Slide
Lager Image
It is sufficient to show that ρ ( HP ) < 1. Assume that HPx = λx , where x is a nonzero vector. Then, one obtains
PPT Slide
Lager Image
By premultiplying x on both sides of equation (8),
PPT Slide
Lager Image
Since A is positive definite, it can be easily shown that λ ≠ 1. Taking the complex conjugate transpose on both sides of equation (9),
PPT Slide
Lager Image
Adding two equations (9) and (10), one obtains
PPT Slide
Lager Image
Let
PPT Slide
Lager Image
Then E is a diagonal matrix whose diagonal element is given by
PPT Slide
Lager Image
for every i . Since
PPT Slide
Lager Image
for all i , every diagonal element of E is positive and so E is positive definite. Hence, (11) implies that
PPT Slide
Lager Image
By simple calculation, one easily obtains | λ | < 1. Hence, the proof is complete.
Since the ESOR method with P = D −1 becomes the SOR method, the following well-known property is immediately obtained from Theorem 2.1.
Corollary 2.2 ( [6] ). Let A = D L U be a symmetric positive definite matrix. If 0 < ω < 2, then the SOR method converges for any x 0 .
Corollary 2.3. Let A = ( aij ) = D L U be a symmetric positive definite matrix. If
PPT Slide
Lager Image
then the ESOR method with P = PF converges for any x 0 .
Proof . Since
PPT Slide
Lager Image
the proof is directly obtained from Theorem 2.1. □
Corollary 2.4. Let A = ( aij ) be a symmetric positive definite matrix. If 0 < ω < 2, then the ESOR method with P = PF converges for any x 0 .
Proof . Since
PPT Slide
Lager Image
Hence, this corollary follows from Corollary 2.3. □
Corollary 2.5. Let A = ( aij ) be a symmetric strictly diagonally dominant or irreducibly diagonally dominant matrix with positive diagonal elements. If
PPT Slide
Lager Image
then the ESOR method with P = PF converges for any x 0 .
Proof . Since a symmetric strictly diagonally dominant or irreducibly diagonally dominant matrix with positive diagonal elements is positive definite, this corollary follows from Corollary 2.3. □
Corollary 2.6. Let A = ( aij ) = D L U be a symmetric positive definite matrix. If A is strictly diagonally dominant and
PPT Slide
Lager Image
then the ESOR method with P = PI converges for any x 0 .
Proof . Note that
PPT Slide
Lager Image
From Theorem 2.1, the ESOR method with P = PI converges when
PPT Slide
Lager Image
Since
PPT Slide
Lager Image
the proof is complete. □
PPT Slide
Lager Image
the upper bound of ω in Corollary 2.6 is greater than 1.
Corollary 2.7. Let A be a symmetric strictly diagonally dominant matrix with positive diagonal elements. If
PPT Slide
Lager Image
then the ESOR method with P = PI converges for any x 0 .
Corollary 2.8. Let A = ( aij ) = D L U be a symmetric positive definite matrix with D = βI, where β is a positive constant. If A is strictly diagonally dominant, then the ESOR method with P = PI is the same as the SOR method which converges for any x 0 when 0 < ω < 2.
Proof . Since D = βI , ∥ A + sg( A ) = 2 β . It follows that PI = β −1 I = D −1 . Thus, the ESOR method with P = PI is the same as the SOR method. From Corollary 2.2, the ESOR method with P = PI converges when 0 < ω < 2. □
3. Numerical experiments
In this section, we provide numerical experiments to evaluate the performance of the ESOR method with diagonal preconditioners. All numerical experiments are carried out using Matlab. In Tables 1 to 4 , ESOR( PF ) and ESOR( PI ) stand for the ESOR methods with diagonal preconditioners PF and PI , respectively. Bold numbers in Tables 1 to 4 refer to the optimal performances for 3 different iterative methods. The first example considers the SPD matrix with constant diagonal and nonpositive off-diagonal entries.
Example 3.1. Consider the two dimensional Poisson’s equation
PPT Slide
Lager Image
with the Dirichlet boundary condition on ∂Ω. When the central difference scheme on a uniform grid with m × m interior node is applied to the discretization of the equation (13), we obtain a linear system Ax = b whose coefficient matrix A ∈ ℝ n × n is given by
PPT Slide
Lager Image
where ⊗ denotes the Kronecker product, n = m 2 , P = tridiag(−1, 4,−1) and Q = tridiag(−1, 0,−1) are m × m tridiagonal matrices. Note that this matrix A is a symmetric irreducibly diagonally dominant matrix. It is easy to compute that
PPT Slide
Lager Image
and α = 0.25. Since A has a constant diagonal (i.e., D = 4 I ), ESOR method with PI is the same as SOR method from Corollary 2.7. Numerical results for Example 3.1 with n = 10 2 or n = 15 2 are provided in Table 1 .
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.1.
PPT Slide
Lager Image
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.1.
The second example considers the randomly generated SPD matrix with negative off-diagonal entries.
Example 3.2. Consider the SPD matrix A ∈ ℝ n × n which is generated by using the following Matlab functions:
PPT Slide
Lager Image
Notice that
PPT Slide
Lager Image
and α ≈ 0.1220 for n = 100 or 0.1235 for n = 200. Numerical results for Example 3.2 with n = 100 or n = 200 are provided in Table 2 .
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.2.
PPT Slide
Lager Image
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.2.
The third example considers the randomly generated SPD matrix with positive off-diagonal entries.
Example 3.3. Consider the SPD matrix A ∈ ℝ n × n which is generated by using the following Matlab functions:
PPT Slide
Lager Image
Notice that
PPT Slide
Lager Image
for n = 100 or 2.0001 for
PPT Slide
Lager Image
and α ≈ 0.8366 for n = 100 or 0.9100 for n = 200. Numerical results for Example 3.3 with n = 100 or n = 200 are provided in Table 3 .
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.3.
PPT Slide
Lager Image
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.3.
The last example considers the randomly generated SPD matrix whose offdiagonal entries contain both positive and negative numbers. More specifically, each of positive and negative entries takes 50% of all off-diagonal entries.
Example 3.4. Consider the SPD matrix A ∈ ℝ n × n which is generated by using the following Matlab functions:
PPT Slide
Lager Image
Notice that
PPT Slide
Lager Image
for n = 100 or 2.0002 for
PPT Slide
Lager Image
and α ≈ 0.8037 for n = 100 or 0.8900 for n = 200. Numerical results for Example 3.4 with n = 100 or n = 200 are provided in Table 4 .
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.4.
PPT Slide
Lager Image
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.4.
4. Conclusions
In this paper, we proposed the ESOR method with diagonal preconditioners and provided its convergence results. Numerical results are in good agreement with the theoretical results provided in Section 2 (see Tables 1 to 4 ). For SPD matrices with negative or nonpositive off-diagonal entries, the ESOR method does not have advantages compared eith the SOR method (see Tables 1 and 2 ). For SPD matrices containing many positive off-diagonal entries, the ESOR method with PF performs better than the other two methods (see Tables 3 to 4 ). These observations are similar to those of the extended Jacobi method studied in [4] . It was also observed that the optimal number of ω is greater than 1 for SPD matrices with negative or nonpositive off-diagonal entries, while the optimal number of ω is not greater than 1 for SPD matrices containing many positive off-diagonal entries. All of these observations have not been proved theoretically, so further research should be required to prove these observations and find out additional advantages of the ESOR method with diagonal preconditioners.
BIO
SeYoung Oh received M.Sc. from Seoul National University and Ph.D at University of Minnesota. Since 1992 he has been at Chungnam National University. His research interests include numerical optimization and biological computation.
Department of Mathematics, Chungnam National University, Daejeon 305-764, Korea
e-mail: soh@cnu.ac.kr
Jae Heon Yun received M.Sc. from Kyungpook National University, and Ph.D. from Iowa State University. He is currently a professor at Chungbuk National University since 1991. His research interests are computational mathematics, iterative method and parallel computation.
Department of Mathematics, College of Natural Sciences, Chungbuk National University, Cheongju 362-763, Korea
e-mail: gmjae@chungbuk.ac.kr
Kyoum Sun Kim is a graduate student in Chungbuk National University. Her research interests are computational mathematics, new homotopy methods for solving functional equations.
Department of Mathematics, Chungbuk National University, Cheongju, 361-763, Korea.
e-mail: giunsun@naver.com
References
Gunawardena A. , Jain S. , Snyder L. (1991) Modified iterative methods for consistent linear systems Linear Algebra Appl. 154/156 123 - 143    DOI : 10.1016/0024-3795(91)90376-8
Kincaid D. , Cheney W. 2002 Numerical Analysis: Mathematics of Scientific Computing 3rd Edition Brooks/Cole CA
Saad Y. 1996 Iterative methods for sparse linear systems PWS Publishing Company Boston
Tarazaga T. , Cuellar D. (2009) Preconditioner generated by minimizing norm Comput. Math. Appl. 57 1305 - 1312    DOI : 10.1016/j.camwa.2008.10.096
Usui M. , Niki H. , Kohno T. (1994) Adaptive Gauss Seidel method for linear systems Intern. J. Computer Math. 51 119 - 125    DOI : 10.1080/00207169408804271
Varga R.S. 2000 Matrix iterative analysis Springer Berlin
Young D.M. 1971 Iterative solution of large linear systems Academic Press New York
Yun J.H. , Lim H.J. , Kim K.S. (2014) Performance comparison of preconditioned iterative methods with direct preconditioners J. Appl. Math. & Informatics 32 389 - 403    DOI : 10.14317/jami.2014.389