NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS Numer. Linear Algebra Appl. 2008; 15:1–11 Published online 24 October 2007 in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/nla.560
Perturbation analysis for the generalized Schur complement of a positive semi-definite matrix Musheng Wei1, ∗, † and Minghui Wang1, 2 1 Department
of Mathematics, East China Normal University, Shanghai 200062, China of Mathematics, Qufu Normal University, Shandong 273165, China
2 Department
SUMMARY Let
P=
A
B
BH
C
0
and S = C − B H A† B be the generalized Schur complement of A0 in P. In this paper, some perturbation bounds of S are presented which generalize the result of Stewart (Technical Report TR-95-38, University of Maryland, 1995) and enrich the perturbation theory for the Schur complement. Also, an error estimate for the smallest perturbation of C, which lowers the rank of P, is discussed. Copyright q 2007 John Wiley & Sons, Ltd. Received 3 April 2007; Revised 17 September 2007; Accepted 19 September 2007 KEY WORDS:
generalized Schur complement; SVD; Moor–Penrose inverse
1. INTRODUCTION In this paper, we use the following notation. Cm×n is the set of m ×n matrices of complex entries. For any matrix A ∈ Cm×n , rank(A) is the rank of A, R(A) is the range of A, AH is the conjugate transpose of A, A† is the Moore–Penrose inverse of A. A0 (>0) implies that A is a Hermitian positive definite (semi-definite) matrix. · = ·2 is the Euclidian vector norm or the spectral matrix norm. ∗ Correspondence †
to: Musheng Wei, Department of Mathematics, East China Normal University, Shanghai 200062, China. E-mail:
[email protected]
Contract/grant sponsor: National Natural Science Foundation of China; contract/grant number: 10771073 Contract/grant sponsor: Science and Technology Commission of Shanghai Municipality; contract/grant number: 04JC14031
Copyright q
2007 John Wiley & Sons, Ltd.
2
M. WEI AND M. WANG
For a given block matrix
A P= C
B D
with A invertible, the Schur complement of A in P is S = D −CA−1 B. When A is not invertible, then the generalized Schur complement of A in P is S = D −CA† B. The Schur complement is a useful tool in matrix analysis. A great deal of work on this topic has been done in the literature, see [1–10] and the references cited therein. The perturbation analysis of the Schur complement has been deduced in the literature [11]. When the matrix P is positive semi-definite, Stewart [12] established a sharper bound that is given in the following theorem. Theorem 1.1 Suppose that the matrices A ∈ Cn 1 ×n 1 , C ∈ Cn 2 ×n 2 , B ∈ Cn 1 ×n 2 are given, and A B P= 0 BH C A>0. Let
Pˆ =
A +A B H +B H
Aˆ ≡ C +C Bˆ H B +B
Bˆ Cˆ
be the perturbed version of P with A = AH , and AA,
BB,
CC
where >0. Denote = AA−1 . If <1,
=
21/2 + , 1−
<1
then Sˆ − S + C 1−
(1)
In this paper, we will generalize the analysis of Stewart to the case in which P0 and A0 and derive the perturbation bound of S = C − B H A† B. Also we will study the error estimate for the smallest perturbation of C which lowers the rank of P. The paper is arranged as follows: In Section 2, we provide some preliminary results which will be used in the paper; in Section 3, we obtain some perturbation bounds for S. An error estimate for the smallest perturbation of C which lowers the rank of P is obtained in Section 4. Finally, we provide some concluding remarks in Section 5. 2. PRELIMINARIES In this section, we mention the following results for further discussion. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:1–11 DOI: 10.1002/nla
PERTURBATION ANALYSIS FOR THE GENERALIZED SCHUR COMPLEMENT
3
Lemma 2.1 (Albert [13] and Horn and Johnson [14]) Suppose that the matrices A ∈ Cn 1 ×n 1 , C ∈ Cn 2 ×n 2 , B ∈ Cn 1 ×n 2 are given, and A B P= BH C Then the following statements are equivalent: (1) P0; (2) A0, C − B H A† B0, R(B) ⊆ R(A); (3) A0, C0, and there is a matrix L ∈ C n 1 ×n 2 with L1, such that B = A1/2 LC 1/2 . As a direct consequence of the above lemma, we have the following. Lemma 2.2 For a given block matrix
A
B
BH
C
0
we have B2 AC
(2)
Lemma 2.3 (Stewart and Sun [15]) ˆ A ∈ Cm×n with rank(A) = rank( A). ˆ Then Suppose that A, AA† − Aˆ Aˆ † AA† (I − Aˆ Aˆ † ) Aˆ − A min{A† , Aˆ † } ˆ A† A(I − Aˆ † A) ˆ A† A − Aˆ † A Aˆ − A min{A† , Aˆ † }
(3)
3. PERTURBATION THEORY FOR THE GENERALIZED SCHUR COMPLEMENT Now, we deduce the perturbation bound for the generalized Schur complement of a positive semi-definite matrix. Theorem 3.1 Suppose that the matrices A ∈ Cn 1 ×n 1 , C ∈ Cn 2 ×n 2 , B ∈ Cn 1 ×n 2 are given, and A B 0 P= BH C A0. Let Pˆ = Copyright q
A +A
B +B
B H +B H
C +C
2007 John Wiley & Sons, Ltd.
≡
Aˆ
Bˆ
Bˆ H
Cˆ
Numer. Linear Algebra Appl. 2008; 15:1–11 DOI: 10.1002/nla
4
M. WEI AND M. WANG
be the perturbed version of P with A = AH , and AA,
BB,
CC
where >0. Denote = AA† . If ˆ =r, rank(A) = rank( A) 1 =
<1
21/2 ++5/2 −2 7/2 −2 5/2 , 1−
1 <1
ˆ then A0 and 1 Sˆ − S + C 1−1
(4)
Proof ˆ respectively. Then from the Let r and ˆ r be the smallest non-zero eigenvalues of A and A, perturbation of eigenvalues for Hermitian matrices [15], ˆ r r −Ar (1−r−1 A) = r (1−) ˆ and hence A0. Also, we have −1/2
Aˆ (1/2)† = ˆ r
r−1/2 A(1/2)† = 1− 1−
Denote = − Bˆ H Aˆ † Bˆ + B H A† B and = . Because C − B H A† B0, B H A† B = A(1/2)† B2 CC+ ˆ = Aˆ (1/2)† B ˆ 2 B H A† B+C+ Bˆ H Aˆ † B
(5)
Now Sˆ − S = Cˆ − Bˆ H Aˆ † Bˆ −(C − B H A† B) = C − Bˆ H Aˆ † Bˆ + B H A† B = C +
(6)
From Lemma 1.1, P0 implies that A = AH and R(B) ⊆ R(A); therefore, B = AA† B and AA† = Hence, we have B H (I − A† A) = B H AA† (I − A† A) = 0 (7) B H A† (I − Aˆ Aˆ † ) Bˆ = B H A† (I − Aˆ Aˆ † )(AA† B +B)
A† A.
It follows from (7) that B H ( Aˆ † − A† ) Bˆ = B H AA† (−A† ( Aˆ − A) Aˆ † − A† (I − Aˆ Aˆ † )+(I − A† A) Aˆ † ) Bˆ = −B H A† A Aˆ † Bˆ − B H A† (I − Aˆ Aˆ † ) Bˆ Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:1–11 DOI: 10.1002/nla
PERTURBATION ANALYSIS FOR THE GENERALIZED SCHUR COMPLEMENT
5
and = − Bˆ H Aˆ † Bˆ + B H A† B = −( Bˆ − B)H Aˆ † Bˆ − B H A† ( Bˆ − B)− B H ( Aˆ † − A† ) Bˆ = −B H Aˆ † Bˆ − B H A† B + B H A† A Aˆ † Bˆ + B H A† (I − Aˆ Aˆ † ) Bˆ
(8)
By applying the inequalities in (2), (3) and (5), we observe that ˆ B Aˆ (1/2)† Aˆ (1/2)† B ˆ B H Aˆ † B
ˆ BA(1/2)† Aˆ (1/2)† B 1−
ˆ A1/2 C1/2 A(1/2)† Aˆ (1/2)† B 1−
1/2 (C+) 1−
(9)
B H A† B BB H A(1/2)† A(1/2)† 1/2 (C+)
(10)
ˆ AB H A(1/2)† A(1/2)† Aˆ (1/2)† B ˆ Aˆ (1/2)† B H A† A Aˆ † B
ˆ B H A(1/2)† Aˆ (1/2)† B (C+) 1− 1−
(11)
ˆ = B H A† AA† (I − Aˆ Aˆ † )2 (AA† B +B) B H A† (I − Aˆ Aˆ † ) B B H A(1/2)† A(1/2)† (A† 2 A2 B+A† AB) (2 5/2 +2 3/2 )(C+)
(12)
From (9)–(12) and (8), we have 1/2 1/2 2 5/2 2 3/2 + + + + = (C+) 1− 1− =
21/2 ++2 5/2 −3 7/2 −3 5/2 (C+) 1−
= 1 (C+) therefore, =
1 Sˆ − S C+ + C C 1−1
1 C, 1−1
Theorem 3.2 Under the conditions of Theorem 3.1, if furthermore, ˆ ⊂ R( A), ˆ R( B) Copyright q
<1,
2007 John Wiley & Sons, Ltd.
2 =
21/2 +−3/2 , 1−
2 <1
Numer. Linear Algebra Appl. 2008; 15:1–11 DOI: 10.1002/nla
6
M. WEI AND M. WANG
ˆ then A0, and we have the following estimate: 2 Sˆ − S + C 1−2
(13)
Proof ˆ ⊆ R( A) ˆ implies that Bˆ = Aˆ Aˆ † B. ˆ Therefore, the term in (12) becomes zero. From Note that R( B) (9)–(11) and (8), we have = =
1/2 +1/2 + (C+) 1− 1−
21/2 +−2 3/2 (C+) = 2 (C+) 1−
therefore, =
2 C, 1−2
2 Sˆ − S C+ + C C 1−2
Remark 3.1 It is obvious that the error estimates obtained in Theorems 3.1 and 3.2 generalize that in Theorem 1.1. It is easy to verify that 2 > 1− 1−2 Hence, the bound in Theorem 3.2 is sharper than that in Theorem 1.1.
4. ERROR ESTIMATES FOR THE SMALLEST PERTURBATION OF C WHICH LOWERS THE RANK OF P In this section, we discuss an error estimate for the smallest perturbation of C which lowers the rank of P. To state this problem clearly, we first give Theorem 4.1 as follows. Lemma 4.1 (Marsaglia and Styan [16]) Let A ∈ Cm×n , B ∈ Cm×k , C ∈ Cl×n and D ∈ Cl×k . Then A B rank = rank(A)+rank(M)+rank(N )+rank(J (D)) C D where M = (I −AA† )B,
N = C(I − A† A)
J (D) = (I −NN † )S(I − M † M) Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:1–11 DOI: 10.1002/nla
PERTURBATION ANALYSIS FOR THE GENERALIZED SCHUR COMPLEMENT
Theorem 4.2 Given
P=
A
B
BH
C
7
0
Then rank(A)rank(P) = rank(A)+rank(S)
(14)
For any integer r satisfying rank(A)r
t p+1 , then C is unique. Proof From Lemma 2.1 one can obtain S0, A0, B = AA† B; hence, ti 0 (i = 1, . . . , n 2 ), M = (I −AA† )B = 0, N = B H (I − A† A) = 0. In terms of Lemma 4.1, (14) holds. Also from (14), A B rank =r B H C −C ¯ = p, where S¯ = C −C − B H A† B, and from Theorem 2.5.3 in [17], is equivalent to rank( S) min
rank(S−C)= p
C = t p+1
Moreover, from the proof of Theorem 2.5.3 in [17], one obtains that a smallest perturbation C = W diag(0, . . . , 0, t p+1 , . . . , tn 2 )W H , and C is unique if t p >t p+1 . Because C −C − B H A† B = W diag(t1 , . . . , t p , 0, . . . , 0)W H 0 one can obtain that
in terms of Lemma 2.1.
A
B
BH
C −C
0
Remark 4.1 Because P0, M = (I −AA† )B = 0, N = B H (I − A† A) = 0; therefore, Theorem 4.2 is a special case of Theorem 2.1 in [18] and formula (∗) in P. 206 of [19]. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:1–11 DOI: 10.1002/nla
8
M. WEI AND M. WANG
ˆ For P, Pˆ in Theorem 3.1 and any r ∈ Finally, we will provide a bound for C −C. [rank(A), rank(P)], p =r −rank(A), let S = W diag(t1 , . . . , tn 2 )W H
and
Sˆ = Wˆ diag(tˆ1 , . . . , tˆn 2 )Wˆ H
(16)
ˆ respectively, where t1 · · · tn 2 0, tˆ1 · · · tˆn 2 0 and be the Schur decomposition of S and S, W = [W1 , W2 ],
Wˆ = [Wˆ 1 , Wˆ 2 ],
T2 = diag(t p+1 , . . . , tn 2 ),
T1 = diag(t1 , . . . , t p )
Tˆ1 = diag(tˆ1 , . . . , tˆp ),
Tˆ2 = diag(tˆp+1 , . . . , tˆn 2 )
(17)
where W1 , Wˆ 1 ∈ C n 2 × p , then there exists a smallest perturbation C = W diag(0, . . . , 0, t p+1 , . . . , tn 2 )W H = W2 T2 W2H
(18)
of C, and a smallest perturbation Cˆ = Wˆ diag(0, . . . , 0, tˆp+1 , . . . , tˆn 2 )Wˆ H = Wˆ 2 Tˆ2 Wˆ 2H ˆ so that of C,
rank rank
A
B
BH
C −C
Aˆ
Bˆ
Bˆ H
Cˆ −Cˆ
= r,
= r,
A
B
BH
C −C
Aˆ
Bˆ
Bˆ H
Cˆ −Cˆ
(19)
0 0
If t p >t p+1 , tˆp >t p+1 , then C and Cˆ are unique. ˆ could be large even when S − S ˆ ˆ ∼ t p −t p+1 , then C −C Examples show that when S − S ˆ ˆ is small. In the following theorem, we will show that if S − S<(t p −t p+1 )/2, then the C −C ˆ is of order O(S − S). Theorem 4.3 Under the notes of (16)–(19), one obtains ˆ ˆ C −CS − S+max{T 2 , Tˆ2 } ˆ Furthermore, if t p >t p+1 and S − S<(t p −t p+1 )/2, then ˆ t p+1 +S − S ˆ ˆ 1+ C −CS − S ˆ t p −t p+1 −S − S
(20)
(21)
Proof ˆ hence, (20) and (21) hold. For p>0, note that If p = 0, then C = S and Cˆ = S, ˆ Wˆ ˆ = W H (S − S) ≡ S − S ⎛ ⎞ T W H Wˆ − W H Wˆ Tˆ T W H Wˆ − W H Wˆ Tˆ 1 1 1 1 2 2 2 1 1 1 1 1 ⎝ ⎠ = T2 W2H Wˆ 1 − W2H Wˆ 1 Tˆ1 T2 W2H Wˆ 2 − W2H Wˆ 2 Tˆ2 Copyright q
2007 John Wiley & Sons, Ltd.
(22)
Numer. Linear Algebra Appl. 2008; 15:1–11 DOI: 10.1002/nla
PERTURBATION ANALYSIS FOR THE GENERALIZED SCHUR COMPLEMENT
and
0 ˆ Wˆ = ˆ = W H (C −C) C −C T2 W2H Wˆ 1
−W1H Wˆ 2 Tˆ2 T2 W2H Wˆ 2 − W2H Wˆ 2 Tˆ2
9
(23)
It is obvious that ¯ = max {Ti WiH Wˆ j − WiH Wˆ j Tˆ j }
(24)
i, j=1,2
One then obtains from (23) and (24)
0 ˆ T2 W2H Wˆ 2 − W2H Wˆ 2 Tˆ2 + C −C T2 W2H Wˆ 1
−W1H Wˆ 2 Tˆ2 0
¯ +max{T2 W2H Wˆ 1 , W1H Wˆ 2 Tˆ2 } +max{T1 , Tˆ2 } This is the inequality in (20). Furthermore, if <(t p −t p+1 )/2, then one obtains tˆp − tˆp+1 t p −t p+1 −2>0,
tˆp −t p+1 t p −t p+1 −>0
from |t j − tˆj | ( j = 1, . . . , n 2 ), and from (24), T2 W2H Wˆ 1 Tˆ1−1 − W2H Wˆ 1 T2 W2H Wˆ 1 − W2H Wˆ 1 Tˆ1 Tˆ1−1 ¯/tˆp Therefore, one obtains W2H Wˆ 1 ¯/tˆp +T2 W2H Wˆ 1 Tˆ1−1
(25)
From (25), one obtains W2H Wˆ 1
¯ ¯ tˆp −t p+1 t p −t p+1 − t p −t p+1 −
(26)
Similarly, one obtains W1H Wˆ 2
¯ t p −t p+1 −
t p −t p+1 −
(27)
Then from (23)–(27), one obtains ˆ ¯ +max{T2 W2H Wˆ 1 , W1H Wˆ 2 Tˆ2 } C −C ¯ max{T2 , Tˆ2 } ¯ + t p −t p+1 − t p+1 + ¯ 1+ t p −t p+1 − t p+1 + 1+ t p −t p+1 − One then obtains the desired estimate in (21). Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:1–11 DOI: 10.1002/nla
10
M. WEI AND M. WANG
Remark 4.2 ˆ is small, the quantity |t j − tˆj |S − S ˆ for j = 1, . . . , n 2 , that is, the perturbations of When S − S ˆ could be large. However, if t p −t p+1 , the the eigenvalues of S are also small. Note that C −C ˆ ˆ is gap between the eigenvalues, is large enough such that S − S<(t p −t p+1 )/2, then C −C also small.
5. CONCLUDING REMARKS Stewart [12] gave a perturbation bound of the Schur complement under the conditions that P0 and A>0. In this paper, we generalize the analysis to the case in which P0 and A0. The derived bounds are sharper than those in [12]. We also discuss an error estimate for the smallest perturbation of C which lowers the rank of P.
ACKNOWLEDGEMENTS
We are grateful to the editor and the anonymous referee for providing many useful comments and suggestions, which improved the presentation of the article.
REFERENCES 1. Carlson D, Haynsworth E, Markham T. A generalization of the Schur complement by means of the Moore–Penrose inverse. SIAM Journal on Applied Mathematics 1974; 26:169–175. 2. Cottle RW. Manifestation of the Schur complement. Linear Algebra and its Applications 1974; 8:189–211. 3. Ando T. Generalized Schur complements. Linear Algebra and its Applications 1979; 27:173–186. 4. Styan GPH. Schur complements and linear statistical models. In Proceedings of the First International Tampere Seminar on Linear Statistical Models and their Applications, Tampere, Finland, August–September 1983, Puntanen S, Pukkila T (eds). Department of Mathematical Sciences, University of Timpere, 1985; 37–75. 5. Bapat RB. A refinement of Oppenheim’s inequality. In Current Trend in Matrix Theory: Proceedings of the Third Auburn Matrix Theory Conference, Auburn University, Auburn, AL, March 1986, Uhlig F, Grone R (eds). North-Holland: New York, 1987; 29–32. 6. Butler CA, Morley TD. Six generalized Schur complements. Linear Algebra and its Applications 1988; 106: 259–269. 7. Smith R. Some interlacing properties of the Schur complement of a Hermitian matrix. Linear Algebra and its Applications 1992; 177:137–144. 8. Wang B, Zhang F. Schur complements and matrix inequalities of Hadamard products. Linear and Multilinear Algebra 1997; 43:315–326. 9. Redivo-Zaglia M. Pseudo-Schur complements and their properties. Applied Numerical Mathematics 2004; 50: 511–519. 10. Zhang F. The Schur Complement and its Applications. Springer: Berlin, 2005. 11. Higham NJ. Accuracy and Stability of Numerical Algorithms (2nd edn). SIAM: Philadelphia, PA, 2002. 12. Stewart GW. On the perturbation of Schur complement in positive semidefinite matrix. Technical Report TR-95-38, University of Maryland, 1995. 13. Albert A. Condition for positive and nonnegative definite in terms of pseudoinverse. SIAM Journal on Applied Mathematics 1969; 17:434–440. 14. Horn RA, Johnson CR. Topics in Matrix Analysis. Cambridge University Press: Cambridge, U.K., 1988. 15. Stewart GW, Sun J-G. Matrix Perturbation Theory. Academic Press: Boston, 1990. 16. Marsaglia G, Styan GPH. Equalities and inequalities for ranks of matrices. Linear and Multilinear Algebra 1974; 2:269–292. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:1–11 DOI: 10.1002/nla
PERTURBATION ANALYSIS FOR THE GENERALIZED SCHUR COMPLEMENT
11
17. Golub GH, Van Loan CF. Matrix Computations (3rd edn). Johns Hopkins University Press: Baltimore, MD, 1996. 18. Wei M. Perturbation theory for the Eckart–Young–Mirsky theorem and the constrained total least squares problem. Linear Algebra and its Applications 1998; 280:267–287. 19. Demmel JW. The smallest perturbation of a submatrix which lowers the rank and a constrained total least squares problem. SIAM Journal on Numerical Analysis 1987; 24:199–206.
Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:1–11 DOI: 10.1002/nla
NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS Numer. Linear Algebra Appl. 2008; 15:13–34 Published online 22 November 2007 in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/nla.561
A comparative study of efficient iterative solvers for generalized Stokes equations Maxim Larin∗, † and Arnold Reusken Institut f¨ur Geometrie und Praktische Mathematik, RWTH Aachen, Templergraben 55, 52056 Aachen, Germany
SUMMARY We consider a generalized Stokes equation with problem parameters 0 (size of the reaction term) and >0 (size of the diffusion term). We apply a standard finite element method for discretization. The main topic of the paper is a study of efficient iterative solvers for the resulting discrete saddle point problem. We investigate a coupled multigrid method with Braess–Sarazin and Vanka-type smoothers, a preconditioned MINRES method and an inexact Uzawa method. We present a comparative study of these methods. An important issue is the dependence of the rate of convergence of these methods on the mesh size parameter and on the problem parameters and . We give an overview of the main theoretical convergence results known for these methods. For a three-dimensional problem, discretized by the Hood–Taylor P2 –P1 pair, we give results of numerical experiments. Copyright q 2007 John Wiley & Sons, Ltd. Received 6 February 2007; Revised 17 October 2007; Accepted 17 October 2007 KEY WORDS:
generalized Stokes problem; preconditioned MINRES; inexact Uzawa method; multigrid methods; Vanka and Braess–Sarazin smoothers
1. INTRODUCTION Let ⊂ R3 be a bounded polygonal domain with a Lipschitz boundary = *. We consider the following generalized Stokes problem. Given f, find a velocity u and a pressure p such that u−u+∇ p = f
in
∇ ·u = 0
in
u=0
on
∗ Correspondence
(1)
to: Maxim Larin, Institut f¨ur Geometrie und Praktische Mathematik, RWTH Aachen, Templergraben 55, 52056 Aachen, Germany. † E-mail: [email protected] Contract/grant sponsor: German Research Foundation (DFG); contract/grant number: SFB 540
Copyright q
2007 John Wiley & Sons, Ltd.
14
M. LARIN AND A. REUSKEN
The parameters >0 (viscosity) and 0 are given. Often the latter is proportional to the inverse of the time step in an implicit time integration method applied to a nonstationary Stokes problem. Note that this general setting includes the classical (stationary) Stokes problem ( = 0). This problem is discretized on a tetrahedral grid with a pair of conforming finite element spaces that is inf–sup stable. In our experiments we use the P2 –P1 Hood–Taylor pair. The resulting discrete problem is of saddle point type with a symmetric indefinite matrix. In this paper we study efficient iterative solvers for this linear system. In particular, the efficiency (robustness) of the solvers with respect to variation in the mesh size parameter and in the problem parameters and is studied. We consider a multigrid method with Vanka and Braess–Sarazin smoothers, a preconditioned MINRES method and an inexact Uzawa method. In the latter two methods multigrid preconditioners are used for the scalar problems for each velocity component. A comparative study of the preconditioned MINRES and inexact UZAWA method with other preconditioned Krylov subspace methods for this problem class is given in [1]. Numerical studies on the performance of coupled multigrid problems for (generalized) Stokes and Navier–Stokes can be found in, for example [2–6]. We do not know of any literature in which a systematic comparison between coupled multigrid, preconditioned MINRES and inexact Uzawa type of methods for this class of generalized Stokes equations is given. In this paper, we present such a comparative study. We give an overview of the main theoretical results that are available for these methods. From this it follows that concerning theoretical convergence results the state of affairs is much better for the preconditioned MINRES and the inexact Uzawa method than for the coupled multigrid method. We pay special attention to the case = 0, >0 variable. In this case, variation of the parameter corresponds to a rescaling of the velocity unknowns. We show that for all methods considered here the rate of convergence is essentially independent of this rescaling. We also investigate the efficiency of the different methods by means of numerical experiments. It turns out that all methods show good robustness properties with respect to variation in the mesh size and in the parameters and . The paper is organized as follows. In Section 2 the weak formulation and the finite element discretization are given. In Section 3 the coupled multigrid method with Braess–Sarazin and Vanka smoothers is described. For the method with Braess–Sarazin smoother a convergence analysis known from the literature is presented in a different form. In Section 4 we discuss the preconditioned MINRES and inexact Uzawa methods. We recall known convergence results for these methods. A comparison of all these methods from a theoretical point of view is given in Section 5. In Section 6 a numerical study of these methods is presented and conclusions are drawn.
2. WEAK FORMULATION AND FINITE ELEMENT DISCRETIZATION The weak formulation of (1) is as follows. Given f ∈ L 2 ()3 , we seek u ∈ H01 ()3 and p ∈ L 20 () such that (u, v)+(∇u, ∇v)−(div v, p) = (f, v) for all v ∈ H01 ()3 (div u, q) = 0
for all q ∈ L 20 ()
(2)
Here (·, ·) denotes the L 2 scalar product. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
EFFICIENT SOLVERS FOR GENERALIZED STOKES EQUATIONS
15
For discretization of (2) we use a standard finite element approach. Based on a quasi-uniform family of nested tetrahedral grids T0 ⊂ T1 ⊂ · · · we use a sequence of nested finite element spaces (Vl−1 , Q l−1 ) ⊂ (Vl , Q l ),
l = 1, 2, . . .
The pair of spaces (Vl , Q l ), l0, is assumed to be stable. By h l we denote the mesh size parameter corresponding to Tl . We assume that h l−1 / h l is uniformly bounded in l. For the theoretical analysis we assume that the pair has the following approximation property: inf u−v1 + inf p −q L 2 ch l (u2 + p1 )
v∈Vl
q∈Q l
∀u ∈ (H 2 ()∩ H01 ())3 , p∈H 1 ()∩ L 20 ()
We use the notation ·k , k = 1, 2, for the norms in H k (). In our numerical experiments we use the Hood–Taylor P2 –P1 pair. The discrete problem is given by the Galerkin discretization of (2) with the pair (Vl , Q l ). We are interested in the solution of this discrete problem on a given finest discretization level l = L. To solve this discrete problem we introduce the standard nodal bases in these finite element spaces. The representation of the discrete problem on level l in these bases results in a linear saddle point problem of the form ul Al BlT Al xl = bl with Al = , xl = (3) pl Bl 0 The dimensions of the spaces Vl and Q l are denoted by nl and m l , respectively. The matrix Al ∈ Rnl ×nl is the discrete representation of the differential operator I − and is symmetric positive definite. Note that Al depends on the parameters and . The matrix Al depends on these parameters, too, and is symmetric and strongly indefinite. In the remainder of the paper we consider iterative solvers for system (3) on the finest level L. Remark 1 The matrix Al is singular. Below we always consider Al on the subspace Rnl ×1⊥ , where 1⊥ is ml the corresponding finite element functions ql ∈ Q l satisfy the subspace of R of vectors forn which l ×1⊥ → Rn l ×1⊥ is invertible. q dx = 0. The mapping A : R l l 3. A COUPLED MULTIGRID METHOD We consider a multigrid method for the coupled system in (3). Below we discuss the components of this multigrid solver. The grid transfer operations: For the prolongation and restriction of vectors (or corresponding finite element functions) between different levels we use the canonical operators. The prolongation between levels l −1 and l is given by PV 0 Pl = 0 PQ where the matrices PV : Rnl−1 → Rnl and PQ : Rm l−1 → Rm l are matrix representations of the embeddings Vl−1 ⊂ Vl (quadratic interpolation for P2 ) and Q l−1 ⊂ Q l (linear interpolation for P1 ), respectively. For the restriction operator Rl between levels l and l −1 we take the adjoint of Pl (w.r.t. a scaled Euclidean scalar product). Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
16
M. LARIN AND A. REUSKEN
Coarse-grid operators: In the multigrid solver for the problem on the finest level L we need operators on the coarser levels L −1, . . . , 0. We use the matrices Al in (3). These result from the finite element discretization method applied on level l. For these matrices the Galerkin relation Al−1 = Rl Al Pl holds. The smoothers: In this paper we consider two popular smoothers for Stokes type of problems, namely the Braess–Sarazin smoother and a Vanka-type smoother. These smoothers and their properties are discussed in the following two subsections. 3.1. Braess–Sarazin smoother This smoother is introduced in [7]. With Dl = diag(Al ) and a given >0 the smoothing iteration has the form ⎛ ⎞ ⎛ ⎞ −1 ⎧ ⎛ ( j) ⎞ ⎫ ( j+1) ( j) ⎨ Al B T ul ul fl ⎬ u Dl BlT l ⎝ ⎠=⎝ ⎠− ⎝ l ⎠− (4) ( j+1) ( j) ( j) ⎩ Bl 0 0 ⎭ Bl 0 pl pl pl Each iteration (4) requires the solution of the auxiliary problem ⎛ ( j) ⎞ rl uˆ l Dl BlT ⎠ =⎝ ( j) pˆ l Bl 0 Bl ul ( j)
( j)
(5)
( j)
with rl = Al ul + BlT pl −fl . From (5) one obtains ( j)
Bl uˆ l = Bl ul and hence, ( j+1)
Bl ul
( j)
= Bl (ul − uˆ l ) = 0 for all j0
(6)
Therefore, the Braess–Sarazin method can be considered as a smoother on the subspace of vectors that satisfy the constraint equation Bl ul = 0. Problem (5) can be reduced to a problem for the auxiliary pressure unknown pˆ l : ( j)
( j)
Z l pˆ l = Bl Dl−1 rl −Bl ul
(7)
where Z l = Bl Dl−1 BlT . Remark 2 The matrix Z l is similar to a discrete Laplace operator on the pressure space. In practice, system (7) is solved approximately using an efficient iterative solver [7–10]. Once pˆ l is known (approximately), an approximation for uˆ l can easily be determined from ( j) Dl uˆ l = rl − BlT pˆ l . The iteration matrix of the smoother (4) is denoted by Sl . For a two-grid method, with 1 pre- and 2 post-smoothing steps, applied to (3) the iteration matrix is given by −1 Rl Al )Sl1 Ml = Sl2 (I − Pl Al−1
(8)
We derive a convergence result for this multigrid method with the Braess–Sarazin smoother. A multigrid convergence analysis is given in [7]; however, only for the case where Dl is replaced Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
17
EFFICIENT SOLVERS FOR GENERALIZED STOKES EQUATIONS ( j)
by the identity matrix. In that paper the reduction of the velocity error ul −ul in the subspace of vectors that satisfy the constraint equation Bl ul = 0 is analysed. The pressure error does not play a role. In the present paper, due to the parameters contained in the left-upper Al -block we are interested in the dependence of the multigrid convergence behaviour on the scaling of the Al -block. This dependence can be analysed very easily (Lemma 3) if we present the analysis from [7] in a different form in which both the errors in the velocity and pressure components are taken into account. In this modified analysis we consider the smoother as in (4) and not the one (as in [7]) in which Dl is replaced by the identity. The analysis is formulated in terms of a smoothing and approximation property. We use the following norms. By · we denote the Euclidean norm on Rk . On Rnl +m l we also use the following norm: 2 2 ul u I 0 l n l (9) with l := := ul 2 +h l2 pl 2 = l pl 0 h l Im l pl h Corresponding matrix norms are denoted by ·, ·h also. For the Braess–Sarazin smoother we have the following result. Lemma 1 For method (4), with iteration matrix Sl , the following holds: In l 0 1 Al Sl = Al Sl1 0 0 Al Sl1 h = Al Sl1
Dl e(1 −2)+1
(10)
if max (Dl−1 Al ), 1 2
Proof −1/2 −1/2 Al Dl , The result in (10) follows from Bl ul = 0 and (6). Introduce A˜ l = Dl A simple computation shows that for the iteration matrix we have 1/2 −1/2 (Inl − B˜ lT ( B˜ l B˜ lT )−1 B˜ l )(Inl −−1 A˜ l ) 0 0 Dl Dl Sl = 0 Im l 0 0 ( B˜ l B˜ lT )−1 B˜ l (Inl − A˜ l )
(11)
−1/2 B˜ l = Bl Dl .
0 0
The operator Tl := Inl − B˜ lT ( B˜ l B˜ lT )−1 B˜ l is an orthogonal projector on Kern( B˜ l ), thus B˜ l Tl = 0. With Ml := Tl (Inl −−1 A˜ l )Tl , we obtain, for 1 2, −1/2 Ml1 −1 0 0 Dl 1 1 −1 Sl = Sl Sl = 0 Im l ( B˜ l B˜ lT )−1 B˜ l (Inl −−1 A˜ l )Ml1 −2 0 1/2 0 Tl (Inl −−1 A˜ l )Dl (12) × 0 0 Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
18
M. LARIN AND A. REUSKEN
Note that
−1/2
Dl
0
0
Al
Im l
−1/2
0
Dl
0
=
Im l
A˜ l
B˜ lT
B˜ l
0
Combining this with (12) yields
−1/2
0
Dl
0
Im l
Al Sl1 =
A˜ l Ml1 −1 +(Inl − Tl )(Inl −−1 A˜ l )Tl Ml1 −2 0
×
Tl (Inl −−1 A˜ l )Dl
1/2
0
0 0
0
(13)
0
From this and (10) it follows that l Al Sl1 l−1 = Al Sl1 and thus the identity in (11) holds. From (13) we obtain for max (Dl−1 Al ) = max ( A˜ l ) and 1 2, −1/2 D
1/2 Al Sl1 Dl 1/2
Dl
l
0
0 Im l
Al Sl1
A˜ l Ml1 −1 +(Inl − Tl )(Inl −−1 A˜ l )Tl Ml1 −2 Tl Inl −−1 A˜ l Dl
1/2
A˜ l Ml1 −1 +(Inl − Tl )(Inl −−1 A˜ l )Tl Ml1 −2 Dl
(14)
Note that Ml is symmetric positive definite with (Ml ) ⊂ [0, 1]. Using this and Tl A˜ l Tl = (Tl − Ml ) we obtain A˜ l Ml1 −1 +(Inl − Tl )(Inl −−1 A˜ l )Tl Ml1 −2 = ( A˜ l Ml − A˜ l Tl +(Tl − Ml ))Ml1 −2 = ( A˜ l −Inl )(Ml − Tl )Ml1 −2 A˜ l −Inl (Ml − Tl )Ml1 −2 = A˜ l −Inl (Ml − Inl )Ml1 −2 Using this in (14) we obtain the inequality in (11).
e(1 −2)+1
This analysis of the smoothing property applies only if problem (7) is solved exactly. In [10] a similar smoothing property is shown for the case that problem (7) is solved approximately. We further comment on this in Remark 3. We now consider the approximation property. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
19
EFFICIENT SOLVERS FOR GENERALIZED STOKES EQUATIONS
Lemma 2 Take = 0 and = 1 in (2). Assume that is such that problem (2) is H 2 -regular. Then there exists a constant C A independent of l such that In l 0 −1 −1 (15) (Al − Pl Al−1 Rl ) C A Dl −1 0 0 h
holds. Proof ˜ }1i m be the nodal bases in Vl and Q l and Let {i }1i nl , { i l Fl u :=
nl
u i i
and
F˜l p :=
i=1
ml
˜ pi i
i=1
the finite element isomorphisms Rnl → Vl and Rm l → Q l , respectively. On Rnl we use a scaled nl 3 Euclidean inner product v, u l = h l i=1 vi u i , and similarly on Q l . The norms ul (pl ) and Fl u L 2 ( F˜l p L 2 ) are uniformly (w.r.t. u, p and l) equivalent. Let Al (and Al−1 ) be scaled such that
Al u, v l = (∇ Fl u, ∇ Fl v),
Bl u, p l = (div Fl u, F˜l p)
for all u, v ∈ Rnl , p ∈ Rm l
(16)
For fl ∈ Vl let u ∈ H01 ()3 , p ∈ L 20 () be the solution of (∇u, ∇v)−(div v, p) = (fl , v) for all v ∈ H01 ()3 (div u, q) = 0
(17)
for all q ∈ L 20 ()
Let (ul , pl ) be the Galerkin solution of this problem in the pair of spaces (Vl , Q l ). The matrix Al is the matrix representation of the finite element discretization of problem (17), cf. (16). Using this, the approximation property of the spaces (Vl , Q l ) and standard finite element techniques (duality argument) we obtain In l 0 u−ul L 2 +h l p − pl L 2 −1 −1 ch ˜ l2 (18) (Al − Pl Al−1 Rl ) c sup fl L 2 0 0 fl ∈Vl h
Using the scaling of Al as in (16) and standard properties of the finite element nodal basis we obtain Dl ch l−2 with a constant c>0. Thus, we obtain the bound in (15). I
In the approximation property it is important to have the projection factor ( 0nl 00 ) in (15). Without this factor one has to consider the Stokes problem in (17), where in the second equation the right-hand side 0 is replaced by (gl , q) with a gl ∈ Q l . The regularity properties of such a problem are in general less favourable as for the case with a 0 right-hand side. In particular, for H 2 -regularity one has to assume certain compatibility conditions on gl that are not satisfied for all gl ∈ Q l , cf. [11]. We further comment on this in Remark 3. Combination of the smoothing and approximation property yields a two-grid convergence result. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
20
M. LARIN AND A. REUSKEN
Theorem 1 Take = 0 and = 1 in (2). Assume that is such that problem (2) is H 2 -regular. For the iteration matrix of the two-grid method with 2 = 0 the following holds: Ml h
CA e(1 −2)+1
for 1 2
with a constant C A independent of l. Proof Due to (10) we have −1 Ml = (Al−1 − Pl Al−1 Rl )
In l
0
0
0
Al Sl1
The desired result follows from (11) and Lemma 2.
In [7] such a result is proved for a two-grid method in which an additional projection step is used in the coarse-grid correction. In [12], however, it is noted that this projection step is superfluous. Using this two-grid contraction number bound one can derive a multigrid W -cycle convergence result using techniques from [13, 14]. The numerical experiments in Section 6 clearly show that the multigrid W -cycle method with Braess–Sarazin smoother is robust with respect to variation in the problem parameters and . We do not know of any analysis in which such a robustness property is proved. An elementary scaling argument can be used to derive a robustness result for the (less interesting) case = 0, >0 arbitrary. For this scaling argument we introduce the notation Il, =
In l
0
0
Im l
,
I˜l, =
Inl
0
0
Im l
(19)
with Ik the identity matrix in Rk . For = 0 let Ml, be the iteration matrix of the two-grid method with 1 pre- and 2 post-smoothing iterations (4) applied to the matrix Al, :=
Al
BlT
Bl
0
(20)
Note that Ml,1 = Ml as in (8). The effect of the scaling on the two-grid iteration matrix is given in the following lemma. Lemma 3 For = 0 the relation Ml, = Il, Ml,1 Il,−1 holds. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
EFFICIENT SOLVERS FOR GENERALIZED STOKES EQUATIONS
21
Proof Let Sl, be the iteration matrix of the Braess–Sarazin smoother applied to Al, . The following relations hold: Al, = I˜l, Al,1 Il,−1 ,
Sl, = Il, Sl,1 Il,−1 ,
Il,−1 Pl Il−1, = Pl ,
−1 ˜ I˜l−1, Rl Il, = Rl
(21)
Using these we obtain 2 1 −1 −1 Ml, = Sl, (Il − Pl Al−1, Rl Al, )Sl, = Il, Ml,1 Il,
and thus the result is proved. Corollary 1 Introduce the norm
2 2 ul ul h2 −1 := l Il, = ul 2 + 2l pl 2 pl pl h,
with a corresponding matrix norm denoted by ·h, . Then we have Ml, h, = Ml,1 h = Ml h and thus the convergence result in Theorem 1 immediately yields an analogous result for the multigrid method applied to the scaled system. The Braess–Sarazin smoother has also been analysed in the setting of a cascadic multigrid method for Stokes problems in [8, 9]. In this analysis, it is assumed that problem (7) is solved exactly. Remark 3 The analysis presented above applies to the case in which problem (7) is solved exactly. In [10], the smoothing property of the Braess–Sarazin method (and other methods of inexact Uzawa type) with an inexact solve in (7) is analysed. The results from that paper can be combined with a suitable approximation property as derived in [15, 16] that differs slightly from the one in (18). We outline the main results of this analysis and present the approximation and smoothing properties in our notation. The analysis in [16] can be used to derive the following approximation property (with l the scaling matrix from (9)): −1 −1 Rl )l2 h = l (Al−1 − Pl Al−1 Rl )l ch l2 (Al−1 − Pl Al−1
(22)
A proof of this result is given in the Appendix. We introduce the scaled matrix h l−1 BlT Al −1 −1 ˜ l := Al = A l l h l−1 Bl 0 ˜ l instead of Al . For most smoothers, ˜ l be the iteration matrix of the smoother applied to A Let S ˜ l = l Sl −1 . We assume that the in particular those of Braess–Sarazin type, cf. [10], we have S l latter relation holds. For the two-grid iteration matrix we obtain −1 Ml h = l (Al−1 − Pl Al−1 Rl )l l−1 Al Sl1 l−1
1
1
−1 ˜ l ch 2 A ˜l ˜ lS ˜ lS Rl )l A l (Al−1 − Pl Al−1 l
Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
22
M. LARIN AND A. REUSKEN
˜ l is the same as in [10] (cf. (5) in that paper) and results from [10] The scaling in the matrix A can be used to derive smoothing properties. For example, from Lemma 2 and Theorem 2 in [10] we obtain ˜ lS ˜ l1 c h −2 , 1 2 A 1 −1 l for a Braess–Sarazin smoother with an inexact (but sufficiently accurate, cf. [10]) inner solve in (7). This leads to a two-grid convergence result as in Theorem 1 also for the case of an ‘inexact’ Braess– Sarazin smoother. Note, however, that such a result can be shown only for problem parameters = 0, = 1 (or some other fixed positive constant). Remark 4 In [17], a modification of the Braess–Sarazin smoother for the case in which problem (7) is solved (0) approximately is suggested. The starting velocity ul is usually not in or close to the kernel of (0) Bl , i.e. Bl ul can be ‘large’. This may have a significant (negative) influence on the pressure correction term pˆ l in (7), in particular if the parameter is chosen relatively large (cf. numerical experiments in Section 6). To avoid this, the following modification is suggested in [17]. Suppose that a sequence of pre- or post-smoothing iterations have to be performed. After the first of these (0) (1) iterations only the velocity update ul → ul is computed but for the pressure one keeps the old (1) (0) value, pl := pl . In the subsequent −1 iterations the standard method without this modification is applied. 3.2. Vanka smoother The Vanka-type smoothers, originally proposed by Vanka [18] for finite difference schemes, are block Gauß–Seidel type of methods. If one uses such a method in a finite element setting then a block of unknowns consists of all degrees of freedom that correspond with one element. Numerical tests given in [5] show that the use of this element-wise Vanka smoother can be problematic for continuous pressure approximations. In [5], the pressure-oriented Vanka smoother for continuous pressure approximations has been suggested as a good alternative. In this method a local problem corresponds to the block of unknowns consisting of one pressure unknown and all velocity degrees of freedom that are connected with this pressure unknown. We only consider this type of Vanka smoother. We first give a more precise description of this method. We take a fixed level l in the discretization hierarchy. To simplify the presentation we drop the level index l from the notation, i.e. we write, for example, ( up ) ∈ Rn+m instead of ( upll ) ∈ Rnl +m l . ( j)
Let r P : Rm → R be the pressure projection (injection) ( j)
rP p= p j ,
j = 1, . . . , m
For each j (1 jm) let the set of velocity indices that are ‘connected’ to j be given by ( j)
V j = {1in | (r P B)i = 0} Define d j := |V j | and write V j = {i 1
r V : Rn → Rd j is given by ( j)
r V u = (u i1 , u i2 , . . . , u id j )T Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
EFFICIENT SOLVERS FOR GENERALIZED STOKES EQUATIONS
23
The combined pressure and velocity projection is given by ⎞ ⎛ ( j) 0 r V ⎠ ∈ R(d j +1)×(n+m) r ( j) = ⎝ ( j) 0 rP Furthermore, define p ( j) = (r ( j) )T . Using these operators we can formulate a standard multiplicative Schwarz method. Define ( j) ( j)T B A A( j) :=r ( j) A p ( j) =: ∈ R(d j +1)×(d j +1) B ( j) 0 Note that B ( j) is a row vector of length d j . In addition, we ⎛ . ⎜ .. 0 ( j) ( j)T ⎜ diag(A ) B =⎜ D( j) = ⎜ 0 ... ⎝ B ( j) 0 ... ...
define ⎞ .. .⎟ ⎟ .. ⎟ ∈ R(d j +1)×(d j +1) .⎟ ⎠ 0
The full Vanka smoother is a multiplicative Schwarz method with iteration matrix Sfull =
m
(I − p ( j) (A( j) )−1r ( j) A)
(23)
j=1
The diagonal Vanka smoother is similar, but with D( j) instead of A( j) : Sdiag =
m
(I − p ( j) (D( j) )−1r ( j) A)
(24)
j=1
Thus, a smoothing step with a Vanka-type smoother consists of a loop over all pressure degrees of freedom ( j = 1, . . . , m), where for each j a linear system of equations with the matrix A( j) (or D( j) ) has to be solved. The degrees of freedom are updated in a Gauss–Seidel manner. These two methods are well defined if all matrices A( j) and D( j) are nonsingular. The linear systems with the diagonal Vanka smoother can be solved very efficiently using the special structure of the matrix D( j) , whereas for the systems with the full Vanka smoother a direct solver for the systems with the matrices A( j) is required. The computational costs for solving a local (i.e. for each block) linear system of equations is ∼ d j for the diagonal Vanka smoother and ∼ d 3j for the full Vanka smoother. Typical values for d j are given in Table II. As far as we know there is no convergence analysis of a multigrid method with a Vanka smoother applied to two- or three-dimensional Stokes problems. In [19] a convergence analysis, based on Fourier transformations, is given for a model one- or two-dimensional Poisson problem in the mixed finite element formulation. Note that in this case the finite element spaces are different from the ones used for Stokes problems. In [20], an additive version of a Vanka method is studied. It is shown that, under reasonable conditions on the velocity and pressure projection operators, this method indeed satisfies a smoothing property. The analysis, however, does not apply to multiplicative Vanka methods, which are the ones that are used in practice, cf. (23), (24). Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
24
M. LARIN AND A. REUSKEN
Recently, in [21] convergence for certain Vanka-type iterative methods applied to Stokes and Navier–Stokes problems has been proved. Smoothing properties, however, are not considered in that paper. We discuss the effect of a rescaling of the system as in (20) on the behaviour of the two-grid method with a full or diagonal Vanka smoother. Let SV, be the iteration matrix of a Vanka smoother as in (23) or (24) with A = Al replaced by A = Al, as in (20). Let MV, be the iteration matrix of the corresponding two-grid method (on level l): 1 −1 MV, = SV,2 (I − Pl Al−1, Rl Al, )SV,
For this method the same scaling result as for the two-grid method with Braess–Sarazin smoother in Lemma 3 holds. Lemma 4 For = 0 the relation MV, = Il, MV,1 Il,−1
(25)
holds. Proof We consider the full Vanka smoother. The same analysis, with obvious modifications, applies to the ( j) diagonal Vanka smoother also. We write A instead of Al, . Define A :=r ( j) A p ( j) . Using the relations p ( j) Il, = Il, p ( j) ,
−1 ( j) p ( j) Il,−1 = Il, p ,
r ( j) I˜l, = I˜l,r ( j) ,
˜−1 ( j) r ( j) I˜l,−1 = Il, r
we obtain ( j)
( j)
p ( j) (A )−1r ( j) = Il, p ( j) (A1 )−1r ( j) I˜l,−1 Thus, we obtain ( j)
( j)
I − p ( j) (A )−1r ( j) A = Il, (I − p ( j) (A1 )−1r ( j) A1 )Il,−1 This yields SV, = Il, SV,1 Il,−1 . In combination with the properties in (21) we obtain the result in (25). 4. OTHER COUPLED ITERATIVE METHODS In this section we consider a preconditioned minimal residual (PMINRES) method and an inexact Uzawa method for solving the discretized Stokes problem. We drop the level index l in the notation, i.e. the system matrix is denoted by A BT A= B 0 Both methods require preconditioners for the matrix A ∈ Rn×n and for the Schur complement S = B A−1 B T ∈ Rm×m . Note that both A and S are symmetric positive definite (S: on 1⊥ ). Let Q A Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
EFFICIENT SOLVERS FOR GENERALIZED STOKES EQUATIONS
25
and Q S be symmetric positive-definite preconditioners of A and S, respectively. Let A >0, S >0, A and S be spectral bounds such that A Q A A A Q A
(26)
S Q S S S Q S
(27)
and
Below we first specify the choice of Q A and of Q S for the discrete generalized Stokes problem. Then we discuss the PMINRES and inexact Uzawa method. 4.1. Preconditioners for Q A and Q S The matrix A has block-diagonal form with identical blocks. Such a block corresponds to the finite element discretization of a scalar reaction–diffusion problem of the form −u +u = f . For Q A we use one iteration of a symmetric V-cycle multigrid method (for each of the blocks in A). In [22] it is shown that for this preconditioner the inequalities A Q A AQ A
(28)
hold with a constant A >0 independent of l, and . Note that the upper spectral constant is A = 1. For typical multigrid methods, the spectral constant A is close to one (typically A 0.85). We now discuss the choice of Q S . For this we introduce an auxiliary Neumann problem in the pressure space, with a given g ∈ L 2 (): Find w ∈ H 1 ()∩ L 20 () such that (∇w, ∇) = (g, )
for all ∈ H 1 ()∩ L 20 ()
Let N = Nl be the stiffness matrix resulting from a finite element discretization of this problem in the pressure finite element space Q l . Let M = Ml be the mass matrix for the pressure space. Let Q N be a preconditioner of N induced by one symmetric V-cycle multigrid iteration applied to the discrete problem with stiffness matrix N . The (Cahouet–Chabard) Schur complement preconditioner Q S is given by −1 Q −1 +Q −1 S := M N ,
= max{, h l2 }
(29)
In [23, 24] it is shown that under certain regularity assumptions for the Stokes problem this preconditioner has corresponding spectral bounds S >0, S in (27) that are independent of the parameters l, and . 4.2. The PMINRES method In the PMINRES method used for solving a linear system with matrix A we use a block-diagonal preconditioner defined by QA 0 M= (30) 0 QS Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
26
M. LARIN AND A. REUSKEN
For a discussion and an efficient implementation of the PMINRES method we refer to the literature [25, 26]. In an efficient implementation one needs per PMINRES iteration one evaluation of Q −1 A , one evaluation of Q −1 and one matrix–vector product with A (and a few other inexpensive S operations). Let r(k) be the residual in the kth iteration of this method. The convergence of the PMINRES can be analysed based on the well-known residual bound r(k) M−1 min max | pk ()| r(0) M−1 pk ∈k , pk (0)=1 ∈(M−1 A)
(31)
For the spectrum of the preconditioned matrix M−1 A the following result is given in [27, 28]: (M−1 A) ⊂ 12 A − 2A +4 S A , 12 A − 2A +4 S A ∪
A , 12
2 A + A +4 S A
(32)
This general result implies that the rate of convergence of the PMINRES method is robust with respect to variation of parameters (in our case: l, and ) if the spectral constants in (26) and (27) do not depend on these parameters. For our choice of the preconditioners this is indeed the case and thus the PMINRES method with Q A and Q S as explained in Section 4.1 has a rate of convergence that is robust with respect to variation in the parameters l, and . Remark 5 Consider the special case of only a rescaling of the Al -block in the matrix Al as in (20). The multigrid preconditioner and the Cahouet–Chabard Schur complement preconditioner automatically take this scaling into account. Let M be the block preconditioner as in (30) for A = Al, . −1 −1 −1 −1 Then, M−1 A = I M1 A1 I (with I = Il, as in (19)) and thus (M A ) = (M1 A1 ) for all >0. 4.3. The inexact Uzawa method For the derivation of the inexact Uzawa method we consider the exact block factorization of the matrix A A 0 I A−1 B T A= (33) B −I 0 S An approximate Schur complement is given by T Sˆ = B Q −1 A B
(34)
−1 ≈ Sˆ −1 we obtain the Using the block factorization (33) and substituting A−1 ≈ Q −1 A and S approximate inverse of A −1 ˆ −1 −1 Q I −Q B S 0 A A A−1 ≈ (35) −B Q −1 −I 0 Sˆ −1 A
Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
EFFICIENT SOLVERS FOR GENERALIZED STOKES EQUATIONS
27
In general, the application of Q A is feasible, but Sˆ −1 w cannot be determined with acceptable computational costs. Therefore, we use Sˆ −1 w ≈ (w) with (w) the result of a PCG method with ˆ = w such that zero starting vector and preconditioner Q S applied to Sz (w)−z Sˆ z Sˆ
(36)
holds for some prescribed tolerance <1. Based on this, the inexact Uzawa method is as follows. Let x(0) = (u(0) , p(0) )T be an initial (0) (0) approximation, and r(0) = f−Ax(0) = (ru , r p ) the initial residual. For k = 0, 1, . . . : • • • • • •
(k)
Compute v = u(k) + Q −1 A ru . ˆ Solve Sz = Bv approximately: z = (Bv) as in (36). T Update the approximation for the velocity u(k+1) = v− Q −1 A B z. (k+1) (k) = p +z. Update the approximation for the pressure p Compute the residual r(k+1) = f−Ax(k+1) with x(k+1) = (u(k+1) , p(k+1) ). Check stopping criterion.
Remark 6 We briefly comment on the computational costs per iteration of this method. These costs depend on the number of PCG iterations needed to satisfy the tolerance requirement in (36). Assume that this number is q. In [1], it is shown that per iteration we then need q +1 evaluations of Q −1 A , q evaluations of Q −1 , q +1 matrix–vector multiplications with B, q matrix–vector multiplications S with B T and one matrix–vector multiplication with A. Moreover, in [1] it is also argued that in general a value for the tolerance parameter ≈ 12 in (36) is close to optimal (w.r.t. efficiency) resulting in very low values for q (typically, q = 1 or 2). We give a convergence result for this inexact Uzawa method that is proved in [1]. Theorem 2 Assume that (26), (27) hold with A = 1. Define A = 1− A ,
g( A , ) = 2 A + (1+ A )
Consider the inexact Uzawa method with such that (36) holds. For the error we have (k) Q A , e(k+1) Sˆ }g( A , ) max{e(k) max{e(k+1) u p u Q A , e p Sˆ }
and 7 (k) e(k) u Q A +e p Sˆ 2
k g( A , )+ g( A , )2 −4 A
(0) (e(0) u Q A +e p Sˆ ) 2
Note that the assumption A = 1 is satisfied for the multigrid preconditioner Q A that we use, cf. (28). For A → 0 we obtain the contraction factor of the exact Uzawa method: g(0, ) = . Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
28
M. LARIN AND A. REUSKEN
We also have g( A , ) 12 (g( A , )+ g( A , )2 −4 A ) and g( A , ) < 1 1 2 (g( A , )+
g( A , )2 −4 A ) < 1
1−2 A 1+ A
(37)
iff 0 <1−2 A
(38)
iff 0 <
Hence, for A < 12 and sufficiently small (as quantified in (37), (38)) we have a convergent method. Moreover, these bounds for the contraction number are independent of parameters (in our case: l, and ) if A and are independent of these parameters. For the multigrid preconditioner we have A ≈ 0.15, independent of l, and , cf. Section 4.1. A reasonable parameter value is
≈ 12 , cf. Remark 6. Owing to the fact that the Schur complement preconditioner Q S discussed in Section 4.1 has spectral constant S and S independent of l, and , an approximate solution that satisfies (36) can be computed with a low and uniformly (w.r.t. parameters) bounded number of PCG iterations. This implies that this method is optimal in the sense that the amount of work per iteration is proportional to that of a few matrix–vector multiplications and the rate of convergence is robust w.r.t. variation in parameters l, and . Remark 7 Consider the special case of only a rescaling of the Al -block in the matrix Al as in Remark 5. The multigrid preconditioner and the Cahouet–Chabard Schur complement preconditioner automatically take this scaling into account. One may check that the result of the inexact Uzawa method are not influenced by this scaling.
5. COMPARISON OF METHODS Before we turn to numerical experiments in the next section, we compare the methods discussed in Sections 3 and 4 from a theoretical point of view. Three issues are relevant here, namely the arithmetic work per iteration, the rate of convergence and the dependence of this rate of convergence on parameters. We consider the following four methods: multigrid with Braess–Sarazin smoother (denoted by BS-MGM), multigrid with diagonal Vanka smoother (denoted by V-MGM), preconditioned MINRES with preconditioner as explained in Section 4.1 (denoted by PMINRES) and the inexact Uzawa method given in Section 4.3 with preconditioners as in Section 4.1 (denoted by MGUZAWA). Arithmetic work per iteration: For the methods V-MGM, PMINRES and MGUZAWA the arithmetic work per iteration is bounded by c(m l +nl ) with a constant c independent of l. For the BS-MGM such a bound only holds if the linear system in (7) is solved approximately, cf. Remark 2. Convergence analysis: We consider fixed values for the problem parameters and . For the BS-MGM there is a convergence result as in Theorem 1, provided that the linear system in (7) is solved exactly. For the case with an inexact inner solve, the theory outlined in Remark 3 can be applied to prove that the method converges with a rate independent of l. For PMINRES a rate of convergence independent of l follows from (31) and (32). For the MGUZAWA method such a convergence result follows from Theorem 2. A convergence analysis of the V-MGM method is not known to us. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
29
EFFICIENT SOLVERS FOR GENERALIZED STOKES EQUATIONS
Robustness w.r.t. variation in parameters: First, consider the special case of a rescaling of the Al block of the matrix with a parameter as in (20). For all four methods the rate of convergence can be shown to be essentially independent of (cf. Corollary 1, Lemma 4 and Remarks 5 and 7). For the general case of variable problem parameters 0 and >0 there are no robustness results on the convergence of BS-MGM or V-MGM. The rate of convergence of the PMINRES and MGUZAWA methods is robust w.r.t. variation in these parameters. This follows from the results presented in Section 4. Summarizing, we conclude that concerning theoretical convergence results the state of affairs is much better for the PMINRES and MGUZWA methods than for the coupled multigrid methods. Parameters in the methods: The V-MGM and the PMINRES methods are parameter free. In the BS-MGM method one has to choose a value for the parameter in the smoother, cf. (4). In the MGUZAWA method the accuracy parameter in (36) occurs.
6. NUMERICAL EXPERIMENTS We consider the generalized Stokes equation as in (1) on the domain = [0, 1]3 . The right-hand side f is taken such that the continuous solution is ⎞ ⎛ sin( x) sin( y) sin( z) 1⎜ ⎟ u(x, y, z) = ⎝ − cos( x) cos( y) sin( z)⎠ 3 2·cos( x) sin( y) cos( z) p(x, y, z) = cos( x) sin( y) sin( z)+C with a constant C such that p dx = 0. For the discretization we start with a uniform tetrahedral grid with h 0 = 12 and we apply regular refinements to this starting discretization. For the finite element discretization we use the Hood–Taylor P2 –P1 pair. In Table I the dimension of the system to be solved on each level and the corresponding step size are given. In all tests below the iterations were repeated until the condition r(k) <10−10 r(0) with r(k) = b−Ax(k) was satisfied. The methods are implemented in the DROPS package [29]. All calculations were performed on AMD Opteron (2390 MHz, 8 Gb) in double precision. We first consider an experiment to show that for this problem class the multigrid method with full Vanka smoother is very time consuming. In Table II we show the maximal and mean values
Table I. Dimensions: nl , number of velocity unknowns; m l , number of pressure unknowns.
nl ml Copyright q
h 0 = 2−1
h 1 = 2−2
h 2 = 2−3
h 3 = 2−4
h 4 = 2−5
81 27
1029 125
10 125 729
89 373 4913
750 141 35 937
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
30
M. LARIN AND A. REUSKEN
Table II. The maximal and mean values of d j on different grids.
Mean (d j )/ max j d j
h 0 = 2−1
h 1 = 2−2
h 2 = 2−3
h 3 = 2−4
h 4 = 2−5
21.8/82
51.7/157
88.8/157
119.1/165
138.1/166
Table III. CPU time and number of iterations for multigrid with the full and diagonal Vanka smoothers. =0 =1 = 10−1 = 10−2 = 10−3
Sfull , h 3 = 2−4 Sdiag , h 3 = 2−4 Sfull , h 4 = 2−5 Sdiag , h 4 = 2−5 287 283 284 356
(4) (4) (4) (5)
19 19 19 20
(10) (10) (10) (11)
3504 3449 3463 3502
(5) (5) (5) (5)
224 238 238 238
(13) (13) (13) (13)
of d j on the level l. These numbers indicate the dimensions of the local systems that have to be solved in the Vanka smoother, cf. Section 3.2. We use a multigrid W -cycle with 2 pre- and 2 post-smoothing iterations. In Table III we show the computing time (in seconds) and the number of iterations needed for both full Vanka Sfull and diagonal Vanka Sdiag smoothers. As can be seen from these results, the rather high dimensions of the local systems lead to high computing times for the multigrid method with the full Vanka smoother compared to the method with the diagonal Vanka smoother. In numerical experiments we observed that the multigrid W -cycle with only one pre- and post-smoothing iteration with the diagonal Vanka method sometimes diverges. Further tests indicate that often for the method with diagonal Vanka smoothing the choice 1 = 2 = 4 is (slightly) better (w.r.t. CPU time) than 1 = 2 = 2. Based on numerical experiments, in the multigrid W -cycle with Braess–Sarazin smoother we use 1 = 2 = 2 and = 1.25. For other values ∈ [1.1, 1.5] the efficiency is very similar. The linear system in (7) is solved approximately using a conjugate gradient method with a fixed relative tolerance CG = 10−2 . Remark 8 In Remark 4 a modification of the Braess–Sarazin smoother is discussed. In Table IV, we give the computing time and the number of iterations needed for the ‘standard’ and ‘modified’ versions of the Braess–Sarazin smoother, for the case = 2.0 (relatively large compared with close to optimal value = 1.25) and CG = 0.2 (inaccurate solution of inner system). We use a multigrid W -cycle with 2 pre- and 2 post-smoothing iterations. The results show that the modified version of the Braess–Sarazin smoother indeed improves performance (compared with the standard one) if the inner systems (7) are solved with low accuracy and the value for the parameter is relatively large. The modification is not needed if we use the close to optimal value = 1.25. Results for the four methods with respect to variation in the problem parameters l, and are given in Tables V and VI. In the MGUZAWA method we use the parameter value = 0.1. From Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
31
EFFICIENT SOLVERS FOR GENERALIZED STOKES EQUATIONS
Table IV. CPU time and the number of iterations for W (2, 2)/BS-MGM method ( = 2.0). h 4 = 2−4
CG = 0.2
h 4 = 2−5
Standard
Modified
Standard
Modified
=0
=1 = 10−1 = 10−3
23 (27) 23 (27) 16 (14)
14 (9) 14 (9) 14 (8)
div. div. div.
173 (11) 173 (11) 164 (11)
= 10
=1 = 10−1 = 10−3
22 (26) 19 (19) 14 (6)
15 (10) 15 (10) 14 (6)
div. div. 172 (8)
155 (10) 162 (11) 175 (7)
= 100
=1 = 10−1 = 10−3
19 (13) 16 (11) 13 (5)
15 (9) 14 (8) 13 (5)
div. 218 (21) 163 (5)
164 (11) 166 (10) 155 (5)
Table V. CPU time and the number of iterations for MGUZAWA, PMINRES, BS- and V-MGM methods.
MGUZAWA
V-MGM
BS-MGM
PMINRES
= 0, h 3 = 2−4 =1 39 (13) = 10−1 38 (13) = 10−3 43 (14)
19 (5) 19 (5) 19 (5)
20 (11) 20 (11) 17 (8)
49 (74) 52 (79) 53 (80)
= 10, h 3 = 2−4 =1 47 (15) = 10−1 34 (11) = 10−3 34 (13)
19 (5) 17 (4) 15 (3)
20 (11) 20 (11) 21 (7)
57 (79) 61 (89) 51 (74)
= 100, h 3 = 2−4 =1 36 (12) = 10−1 29 (10) = 10−3 38 (15)
17 (4) 15 (3) 15 (3)
20 (11) 19 (7) 19 (6)
51 (73) 49 (69) 58 (85)
these results we conclude the following: (1) Not only the PMINRES and MGUZAWA methods are robust with respect to variation in the parameters and (as predicted by theory), but also both multigrid methods are. (2) For = 0 variation of is the same as rescaling of the Al block as in (20). The results show that for all four methods the rate of convergence is essentially independent of this scaling parameter , as predicted by theory. (3) In most cases V-MGM is the most efficient method and PMINRES has the lowest efficiency. (4) The parameter free PMINRES method shows a close to constant behaviour (only relatively small changes in CPU time and number of iterations) if the parameters and are varied. In this sense, this method is the most robust one. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
32
M. LARIN AND A. REUSKEN
Table VI. CPU time and the number of iterations for MGUZAWA, PMINRES, BS- and V-MGM methods.
MGUZAWA
V-MGM
BS-MGM
PMINRES
= 0, h 4 = 2−5 =1 361 (14) = 10−1 315 (12) = 10−3 319 (12)
198 (5) 199 (5) 198 (5)
274 (14) 276 (14) 241 (11)
445 (75) 476 (81) 441 (74)
= 10, h 4 = 2−5 =1 419 (15) = 10−1 321 (12) = 10−3 265 (11)
190 (5) 189 (5) 145 (3)
244 (13) 224 (10) 238 (7)
538 (82) 548 (87) 540 (87)
= 100, h 4 = 2−5 =1 305 (11) = 10−1 261 (10) = 10−3 329 (14)
190 (5) 167 (4) 122 (2)
241 (13) 243 (13) 282 (9)
484 (75) 488 (77) 441 (68)
APPENDIX We use the ideas from [16] to derive the approximation property in (22). The Stokes problem in (17) can be reformulated in another standard form using the symmetric bilinear form k((u, p), (v, q)) = (∇u, ∇v)−(div v, p)−(div u, q)
on (V× Q)×(V× Q)
with V = H01 ()3 , Q = L 20 (). For given (w,r ) ∈ V× Q there exists a unique projection S(w,r ) = (S1 w, S2r ) ∈ Vl × Q l such that k((S1 w, S2r ), (vl , ql )) = k((w,r ), (vl , ql ))
for all (vl , ql ) ∈ Vl × Q l
Note that w− S1 w1 +r − S2r L 2 c(w1 +r L 2 ) holds. A duality argument, in which the H 2 -regularity of the Stokes problem (17) is used, yields w− S1 w L 2 ch l (w− S1 w1 +r − S2r L 2 ) For f ∈ L 2 ()3 , g ∈ L 2 () let (u, p) ∈ V× Q be the solution of k((u, p), (v, q)) = (f, v) L 2 +(g, q) L 2
for all (v, q) ∈ V× Q
Galerkin discretization of this problem in Vl × Q l results in an approximate solution (ul , pl ) = S(u, p) = (S1 u, S2 p). Note that u−ul L 2 ch l (u−ul 1 + p − pl L 2 ) holds. Using the inf–sup Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
EFFICIENT SOLVERS FOR GENERALIZED STOKES EQUATIONS
33
property of the Stokes operator we obtain u−ul 1 + p − pl L 2 c
k((u−ul , p − pl ), (w,r )) w1 +r L 2 (w,r )∈V×Q sup
=c
k((u− S1 u, p − S2 p), (w− S1 w,r − S2r )) w1 +r L 2 (w,r )∈V×Q
=c
k((u, p), (w− S1 w,r − S2r )) w1 +r L 2 (w,r )∈V×Q
=c
(f, w− S1 w) L 2 +(g,r − S2r ) L 2 w1 +r L 2 (w,r )∈V×Q
c
f L 2 w− S1 w L 2 +g L 2 r − S2r L 2 w1 +r L 2 (w,r )∈V×Q
c
f L 2 h l (w1 +r L 2 )+g L 2 (w1 +r L 2 ) w1 +r L 2 (w,r )∈V×Q
sup
sup
sup
sup
sup
= c(h l f L 2 +g L 2 ) Thus, for the discretization error we obtain the L 2 -error bound u−ul L 2 +h l p − pl L 2 ch l (u−ul 1 + p − pl L 2 )ch l2 (f L 2 +h l−1 g L 2 ) Note that for g = 0 this reduces to the one used in (18). Using standard arguments we obtain the following approximation property (with scaling matrix l as in (9)): −1 −1 Rl )l2 h = l (Al−1 − Pl Al−1 Rl )l (Al−1 − Pl Al−1
c c
sup
u−ul L 2 +h l p − pl L 2 fl L 2 +gl L 2
sup
h l2 (fl L 2 +h l−1 h l gl L 2 ) = ch l2 fl L 2 +gl L 2
(fl ,gl )∈Vl ×Q l
(fl ,gl )∈Vl ×Q l
This proves the result in (22). REFERENCES 1. Peters J, Reichelt V, Reusken A. Fast iterative solvers for discrete Stokes equations. SIAM Journal on Scientific Computing 2005; 27:646–666. 2. John V. A comparison of parallel solvers for the incompressible Navier–Stokes equations. Computing and Visualization in Science 1999; 1:193–200. 3. John V, Matthies G, Mitkova TI, Tobiska L, Vassilevski PS. A comparison of three solvers for the incompressible Navier–Stokes equations. In Large-scale Scientific Computations of Engineering and Environmental Problems II, Griebel M et al. (eds). Notes on Numerical Fluid Mechanics, vol. 73, 2000; 215–222. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
34
M. LARIN AND A. REUSKEN
4. John V, Tobiska L. A coupled multigrid method for nonconforming finite element discretizations of the 2d-Stokes equation. Computing 2000; 64:307–321. 5. John V, Matthies G. Higher order finite element discretizations in a benchmark problem for incompressible flows. International Journal for Numerical Methods in Fluids 2001; 37:885–903. 6. Turek S. Solvers for Incompressible Flow Problems. Springer: Berlin, 1999. 7. Braess D, Sarazin R. An efficient smoother for the Stokes problem. Applied Numerical Mathematics 1997; 23:3–19. 8. Braess D, Dahmen W. A cascadic multigrid algorithm for the Stokes equations. Numerische Mathematik 1999; 82:179–191. 9. Braess D, Dahmen W, Lipnikov K. A subspace cascadic multigrid method for mortar elements. Computing 2002; 69:205–225. 10. Zulehner W. A class of smoothers for saddle point problems. Computing 2000; 65:227–246. 11. Dauge M. Stationary Stokes and Navier–Stokes systems on two- or three-dimensional domains with corners. Part I: linearized equations. SIAM Journal on Mathematical Analysis 1989; 22:74–97. 12. Braess D, Dahmen W, Wieners C. A multigrid algorithm for the mortar finite element method. SIAM Journal on Numerical Analysis 1999; 37:48–69. 13. Hackbusch W. Multigrid Methods and Applications. Springer: Berlin, Heidelberg, New York, 1985. 14. Hackbusch W. Iterative Solution of Large Sparse Systems of Equations. Springer: New York, 1994. 15. Brenner SC. Multigrid methods for parameter dependent problems. RAIRO Mod´elisation Math´ematique et Analyse Num´erique 1996; 30:265–297. 16. Verf¨urth R. A multilevel algorithm for mixed problems. SIAM Journal on Numerical Analysis 1984; 21:264–271. 17. Available at: http://homepage.ruhr-uni-bochum.de/Dietrich.Braess/smooth.ps. 18. Vanka S. Block-implicit multigrid calculation of two-dimensional recirculating flows. Computer Methods in Applied Mechanics and Engineering 1986; 59:29–48. 19. Molenaar J. A two-grid analysis of the combination of mixed finite elements and Vanka-type relaxation. In Multigrid Methods, III, Hackbusch W, Trottenberg U (eds). International Series of Numerical Mathematics, vol. 98. Birkh¨auser Verlag: Basel, 1991; 313–323. 20. Sch¨oberl J, Zulehner W. On Schwarz-type smoothers for saddle point problems. Numerische Mathematik 2003; 95:377–399. 21. Manservisi S. Numerical analysis of Vanka-type solvers for steady Stokes and Navier–Stokes flows. SIAM Journal on Numerical Analysis 2006; 44:2025–2056. 22. Olshanskii M, Reusken A. On the convergence of a multigrid method for linear reaction–diffusion problems. Computing 2000; 65:193–202. 23. Bramble JH, Pasciak JE. Iterative techniques for time dependent Stokes problems. Computers and Mathematics with Applications 1997; 33:13–30. 24. Peters J, Olshanskii MA, Reusken A. Uniform preconditioners for a parameter dependent saddle point problem with application to generalized Stokes interface equations. Numerische Mathematik 2006; 105:159–191. 25. Benzi M, Golub GH, Liesen J. Numerical solution of saddle point problems. Acta Numerica 2005; 14:1–137. 26. Paige C, Saunders M. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis 1975; 12:617–629. 27. Rusten T, Winther R. A preconditioned iterative method for saddlepoint problems. SIAM Journal on Matrix Analysis and Applications 1992; 13:887–904. 28. Silvester D, Wathen A. Fast iterative solution of stabilised Stokes systems. Part II: using general block preconditioners. SIAM Journal on Numerical Analysis 1994; 31:1352–1367. 29. Available at: http://www.igpm.rwth-aachen.de/drops/.
Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:13–34 DOI: 10.1002/nla
NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS Numer. Linear Algebra Appl. 2008; 15:35–54 Published online 28 December 2007 in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/nla.562
Harmonic and refined Rayleigh–Ritz for the polynomial eigenvalue problem Michiel E. Hochstenbach1, ∗, † and Gerard L. G. Sleijpen2 1 Department
of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB, The Netherlands 2 Mathematical Institute, Utrecht University, P.O. Box 80.010, NL-3508 TA Utrecht, The Netherlands
SUMMARY After reviewing the harmonic Rayleigh–Ritz approach for the standard and generalized eigenvalue problem, we discuss several extraction processes for subspace methods for the polynomial eigenvalue problem. We generalize the harmonic and refined Rayleigh–Ritz approaches which lead to new approaches to extract promising approximate eigenpairs from a search space. We give theoretical as well as numerical results of the methods. In addition, we study the convergence of the Jacobi–Davidson method for polynomial eigenvalue problems with exact and inexact linear solves and discuss several algorithmic details. Copyright q 2008 John Wiley & Sons, Ltd. Received 16 January 2006; Revised 17 October 2007; Accepted 17 October 2007 KEY WORDS:
polynomial eigenvalue problem; harmonic Rayleigh–Ritz; refined Rayleigh–Ritz; interior eigenvalues; Jacobi–Davidson; subspace extraction; subspace method; subspace expansion; Rayleigh–Ritz
1. INTRODUCTION: RAYLEIGH–RITZ FOR THE STANDARD EIGENVALUE PROBLEM Let A be a (large sparse) n ×n matrix, and U be a k-dimensional search space for a sought eigenvector x corresponding to an eigenvalue of A. The search space could for instance be generated by the Arnoldi or Jacobi–Davidson method (see, e.g. [1]); typically k n. Let the columns of the n ×k search matrix U form an orthonormal basis for U. The Rayleigh–Ritz extraction determines approximate eigenpairs (, u) with u ∈ U and two-norm u = 1; therefore,
∗ Correspondence
to: Michiel E. Hochstenbach, Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB, The Netherlands. † E-mail: [email protected] Contract/grant sponsor: NSF; contract/grant number: DMS-0405387
Copyright q
2008 John Wiley & Sons, Ltd.
36
M. E. HOCHSTENBACH AND G. L. G. SLEIJPEN
we can write u =U c for a small k-vector c with c = 1. The Galerkin condition on the residual r := Au −u ⊥ U,
u =U c ∈ U
(1)
leads to the projected eigenproblem U ∗ AU c = c The Ritz value is the Rayleigh quotient of u: (u) :=
u ∗ Au u∗u
Here, c is called a primitive Ritz vector (in [2]), and u =U c is a Ritz vector. We now show that the Rayleigh–Ritz method works well for the extraction of well-separated exterior eigenvalues of Hermitian matrices, but may fail for clustered or interior eigenvalues, or for non-Hermitian matrices. The following claim is well known. Claim 1.1 Rayleigh–Ritz works well for the extraction of well-separated exterior eigenvalues of Hermitian matrices. By this we mean that if (, u) is a Ritz pair of a Hermitian matrix, and if ≈ , where is either the leftmost or the rightmost eigenvalue, and also well separated, then necessarily u ≈ x. The reason for this is the following. Let 1 < · · · <n be the eigenvalues of a Hermitian matrix A, with corresponding eigenvectors x1 , . . . , xn . Suppose that u ≈ x is an approximate eigenvector. Decomposing u=
n
i xi
i=1
n we have = i=1 |i |2 i . If ≈ 1 or ≈ n , then we must have 1 ≈ 1 or n ≈ 1 (when the eigenvectors are scaled appropriately), from which we conclude u ≈ x 1 or u ≈ xn , respectively. This justifies Claim 1.1. When the exterior eigenvalues of a Hermitian matrix are clustered, there is no guarantee that u is close to any particular eigenvector, but (using a similar argument as before) we do know that u is almost in the span of the relevant eigenvectors. In this case, block methods may be advantageous. Rayleigh–Ritz does not need to work well for the extraction of interior eigenvalues of Hermitian matrices, as the example in [2, p. 282] shows. Claim 1.1 can also fail for exterior eigenvalues of non-Hermitian A, as the following example, inspired by Sleijpen et al. [3], shows. Let for small , >0 and , >0 √ A = diag(0, −, −+i, −−i), U = [cos()e1 +sin()e2 (e3 +e4 )/ 2] where ei denotes the ith canonical basis vector. Then, although (U, e1 ) = , that is, the search space makes a small angle with the eigenvector of an exterior (the rightmost) eigenvalue, the √ Rayleigh–Ritz method will abusively select the Ritz pair (−, (e3 +e4 )/ 2) as an approximation to the rightmost eigenpair, as long as − sin2 ()<−. Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
HARMONIC AND REFINED RAYLEIGH–RITZ FOR THE PEP
37
On the other hand, Van den Eshof [4, Theorem 2.2.3] has shown that if an eigenvalue is outside the field of values generated by the space orthogonal to the corresponding eigenvector—as is for instance the case in the last example—then the Rayleigh–Ritz approach can asymptotically (that is, close enough to the solution) be used safely. For the example discussed, this means that for small enough the corresponding Ritz vector is a good approximation to the true eigenvector. Also, when the field of values condition fails to hold, Rayleigh–Ritz in practice often performs much better for (relatively well separated) exterior eigenvalues than for interior eigenvalues of non-Hermitian matrices. In an attempt to better approximate interior eigenpairs, the harmonic Rayleigh–Ritz approach was introduced in [5]. The rest of this paper has been organized as follows. In Section 2, we review the harmonic Rayleigh–Ritz approach for the standard and generalized eigenvalue problem, adding a few viewpoints that may give more insight into the method. Sections 3–5 generalize standard Rayleigh–Ritz, harmonic Rayleigh–Ritz, and refined Rayleigh–Ritz for the polynomial eigenvalue problem, where our goal is to find promising approximate eigenpairs corresponding to (interior) eigenvalues from a search space. In Section 6, we revisit the Jacobi–Davidson subspace expansion, studying the effects of exact and approximate linear solves in the inner iteration on the convergence of the method. Finally, we give numerical experiments and a conclusion in Sections 7 and 8.
2. HARMONIC RAYLEIGH–RITZ Suppose we are interested in eigenvalues near a target , for instance in the interior of the spectrum. We assume that is not already an eigenvalue of A itself. Denote the identity matrix by I . Since (A −I )−1 x = (−)−1 x we see that eigenvalues of A near are exterior eigenvalues of (A −I )−1 , a desirable property in view of the previous section. Consider the (Petrov–)Galerkin condition on the residual of the shift-and-inverse matrix (A −I )−1 u −( −)−1 u ⊥ V,
u =U c
(2)
where U is the search space and V is the test space. For large sparse matrices, working with the inverse (A −I )−1 is often highly undesirable. To eliminate the inverse in the Galerkin condition, we want to choose V in a suitable way. While V = (A −I )∗ U gives rise to the standard Rayleigh–Ritz extraction (see (1)), the choice V = (A −I )∗ (A −I )U leads to the following conditions, which are all the same, but expressed in a different way, enabling different interpretations: (i) (ii) (iii) (iv)
(A −I )−1 u −( −)−1 u ⊥ (A −I )∗ (A −I )U, −1 −1 (A −I ) u −(−) u ⊥(A− I )∗ (A− I ) U, (A − I ) u ⊥ (A −I )U, U ∗ (A −I )∗ (A −I )U c = ( −)U ∗ (A −I )∗ U c.
This is called the harmonic Rayleigh–Ritz approach with target . In analogy to the Rayleigh–Ritz terminology, is a harmonic Ritz value, the harmonic Rayleigh quotient or the Temple quotient Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
38
M. E. HOCHSTENBACH AND G. L. G. SLEIJPEN
of a harmonic Ritz vector u: (A −I ) u = ( u ) := + ∗ u (A −I )∗ u 2
(3)
all with respect to target . It is natural to call c a primitive harmonic Ritz vector. Characterization (ii) states that harmonic Rayleigh–Ritz can be seen as standard Rayleigh–Ritz on (A −I )−1 with respect to the inner product (a, b)(A− I )∗ (A− I ) := b∗ (A −I )∗ (A −I )a where the situation that (a, b)(A− I )∗ (A− I ) = 0 is denoted by a ⊥(A− I )∗ (A− I ) b. This forms a motivation for harmonic Rayleigh–Ritz, in view of the facts that Rayleigh–Ritz is favorable for exterior eigenvalues and that eigenvalues near are exterior eigenvalues of (A −I )−1 . Item (iii) states that the (ordinary) residual should be orthogonal to a test space different from the search space. Item (iv), which is used for practical computations (see also [2, p. 293]), expresses that a harmonic Ritz pair ( , u ) is closely connected to an eigenpair of a projected generalized eigenvalue problem. Denote = −. As noted in [2, p. 293], by left-multiplying U ∗ (A −I )∗ (A −I )U c = U ∗ (A −I )∗ U c
(4)
by c∗ and using Cauchy–Schwarz, we see that a solution ( , c) of this generalized eigenproblem satisfies (using u =U c) (A −I ) u | |
(5)
This makes clear that if | | is small, i.e. if the harmonic Ritz value is close to , then the pair (, u ) has a small residual norm and is therefore a good approximation to an eigenpair of A, as the following well-known results show; part (a) is Bauer–Fike and for (b) we recall (see [2, p. 44]) that if is a simple eigenvalue, we have a spectral decomposition A = x y ∗ + X 1 LY1∗ , where x = 1, Y1 is orthonormal, and Y1∗ x = 0. Theorem 2.1 (See e.g. [6, Theorem 3.6; 2, p. 288]) (a) If A = X X −1 is diagonalizable, there exists an eigenvalue such that |−| (X )(A −I ) u where (X ) = X X −1 is the condition number of X . (b) If is a simple eigenvalue and A = x y ∗ + X 1 LY1∗ , where x = 1, Y1 is orthonormal, and Y1∗ x = 0, then sin( u , x)
(A −I ) u (A −I ) u min (L −I ) min (L −I )−|−|
We remark that the quantity min (L −I ) is also known as sep(, L); it is nonzero since is not an eigenvalue of A. Since we assumed that is simple, also min (L −I )>0; therefore → and (A −I ) u → 0 are sufficient to ensure that u → x. Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
HARMONIC AND REFINED RAYLEIGH–RITZ FOR THE PEP
39
The conclusion is that harmonic Rayleigh–Ritz avoids the so-called ‘ghost eigenvalues’, also named ‘imposters’ or ‘impersonators’ in [2]: if there is a harmonic Ritz pair ( , u ) with close to , the corresponding residual norm (A −I ) u (and to a lesser extent (A − I ) u ) is necessarily small, and hence u should be a good approximate eigenvector, and not some linear combination of irrelevant eigenvectors as in the example in Section 1. The next important observation is that the harmonic Rayleigh–Ritz extraction is primarily meant to get a decent approximate eigenvector. It turns out that the harmonic Ritz value can be quite inaccurate (see, for instance, [3]). Indeed, given the approximate eigenvector u , the Rayleigh quotient ( u ) is the best approximation to the eigenvalue, in the sense that it minimizes the residual norm (see, e.g. [7, Fact 1.9]): ( u ) = argmin A u − u
Therefore, it is often advisable to take the Rayleigh quotient of the harmonic Ritz vector as an approximate eigenvalue, instead of the harmonic Ritz value. For the generalized eigenproblem Ax = Bx, we can use a similar harmonic Rayleigh–Ritz approach. On the basis of (A −B)−1 Bx = (−)−1 x, we impose the Galerkin condition (cf. (2)) (A −B)−1 B u −( −)−1 u ⊥ V,
c u = U
With V = (A −B)∗ (A −B)U, the following conditions are the same but expressed in a different manner: (i) (A −B)−1 B u −( −)−1 u ⊥ (A −B)∗ (A −B)U, −1 −1 (ii) (A −B) B u −( −) u ⊥(A− B)∗ (A− B) U, (iii) (A − B) u ⊥ (A −B)U, (iv) U ∗ (A −B)∗ (A −B)U c = ( −)U ∗ (A −B)∗ BU c. Therefore, we are interested in the eigenpair(s) ( , c) of the projected generalized eigenproblem U ∗ (A −B)∗ (A −B)U c = U ∗ (A −B)∗ BU c
(6)
for which , playing the role of −, should be of minimal magnitude. Similar to (5), this gives (A −B) u | |B u | |BU which, again, ‘discourages imposters’ [2, p. 296]. A justification of the harmonic approach for both the standard and generalized eigenvalue problem is that eigenvectors that are present in the search space are detected indeed, see the following proposition, which is a straightforward generalization of [2, p. 293]. Proposition 2.2 Let (, x) be an eigenpair of Ax = Bx, then it is also a harmonic Ritz pair with respect to the search space span(x). Proof This follows for instance from substituting (, x) in characterization (iii).
We note that if x is part of a larger subspace U, the harmonic approach may still have difficulties selecting the right vector if there are (nearly) equal harmonic Ritz values, see [8]. This, however, Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
40
M. E. HOCHSTENBACH AND G. L. G. SLEIJPEN
rarely forms a problem in practical processes, since we may just continue the subspace method by expanding the search space and performing a new extraction process.
3. THE POLYNOMIAL EIGENVALUE PROBLEM Now we switch our attention to the polynomial eigenvalue problem p()x = (l Al +l−1 Al−1 +· · ·+A1 + A0 )x = 0
(7)
where all matrices have size n ×n. In this section, we summarize some known extraction techniques: (standard) Rayleigh–Ritz and two-sided Rayleigh–Ritz. 3.1. Rayleigh–Ritz for the polynomial eigenvalue problem Given an approximate eigenvalue ≈ and an approximate eigenvector u ≈ x, the residual r is defined by r (, u) := p()u = (l Al +l−1 Al−1 +· · ·+ A0 )u Then the Rayleigh–Ritz approach for the polynomial eigenvalue problem imposes the Galerkin condition p()u ⊥ U with u =U c leading to the projected polynomial eigenproblem (l U ∗ Al U +l−1 U ∗ Al−1 U +· · ·+U ∗ A0 U )c = 0 which, as a low-dimensional problem, may for instance be solved using techniques employing a companion matrix. For alternative extraction methods, we consider a Petrov–Galerkin condition p()u ⊥ V where V = U is a suitably chosen test space. For every test vector v ∈ V, this implies p()u ⊥ v. We will examine one option in the next subsection, and come back to the subject in Sections 4 and 6. 3.2. Two-sided Rayleigh–Ritz We now argue that a search space for the left eigenvector is the best possible test space V in the following sense. Given any nonzero v ∈ V, the equation v ∗ p()u = 0 defines = (u, v) implicitly as a function of u and v. Denote by p the derivative of p. When v ∗ p ()x = 0, then by the implicit function theorem we obtain [9] * v ∗ p() (x, v) = − ∗
v p ()x *u
(8)
Hence, when we choose v = y, the left eigenvector of (7) satisfies y ∗ p() = 0, and if y ∗ p ()x = 0, then is stationary in the eigenvector point (x, y) with respect to changes in x (and y). Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
41
HARMONIC AND REFINED RAYLEIGH–RITZ FOR THE PEP
In practice, we will not have the exact left eigenvector to our disposal, but we may try to approximate both the left and the right eigenvectors in the process, this is the essence of two-sided subspace methods, as for instance two-sided Lanczos [1, Chapter VIII; 10] or two-sided Jacobi– Davidson [9, 11, 12]. Equation (8) implies that if u is a first-order accurate approximation to the right eigenvector (that is, u = x +d, with d small), and v is a first-order accurate approximation to the left eigenvector (v = y +e, with e small), then (u, v) is a second-order accurate approximation to the eigenvalue (|−| = O(de)). However, in the rest of the paper we will not consider two-sided methods and assume that we have no information about the left eigenvector at hand.
4. HARMONIC RAYLEIGH–RITZ FOR THE POLYNOMIAL EIGENVALUE PROBLEM Assume that we are interested in (interior) eigenpairs (, x) of (7), where is close to a known target , and where p() is nonsingular (otherwise is an eigenvalue). The aim of this section is to generalize the harmonic Rayleigh–Ritz approach to the polynomial eigenproblem. First, we use a simple Taylor expansion which we will write out for completeness: we have p()x = ( p()− p())x 1 d = p((−)+) d x 0 d 1
= (−)
p ((−)+) d x
0
Hence, p()x 1 |−|
(9)
1 = max p (t) := max p (t (−)+)
(10)
where t∈[,]
Moreover,
t∈[0,1]
1
( p()−(−) p ())x = (−)
( p ((−)+)− p ()) d x
0
= (−)
1 0
1 0
= (−)2 0
1
d
p (((−)+−)+) d d x d 1
(−1)
p
((−1)(−)+) d d x
0
From this it follows that p()x −(−) p ()x 12 2 |−|2 Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
42
M. E. HOCHSTENBACH AND G. L. G. SLEIJPEN
where
2 = max p
(t) := max p
(t (−)+) t∈[,]
t∈[0,1]
Summarizing, we have p()x = (−) p ()x + F x,
F = O(|−|2 )
(11)
Discarding the term F x for the moment, which is one order of |−| smaller than (−) p ()x, this yields p()−1 p ()x ≈ (−)−1 x Therefore, when we look for eigenvalues close to , we can also search for eigenvalues with large magnitude of p()−1 p (). In the (Petrov–)Galerkin equation u −(− )−1 u ⊥ V, p()−1 p ()
u =U c
we want to choose V, such that it is unnecessary to work with the inverse of p(). With the choice V = p()U we get back (when including again the second-order term Fu) the standard Rayleigh–Ritz condition p() u ⊥ U. Therefore, also inspired by Section 2, we take V = p()∗ p()U. This leads to the following four conditions, which are the same but expressed in different ways: (i) p −1 () p () u −(− )−1 u ⊥ p()∗ p()U, −1
−1 (ii) p () p () u −(− ) u ⊥ p()∗ p() U,
(iii) p() u −(− ) p () u ⊥ p()U, (iv) U ∗ p()∗ p()U c = (− )U ∗ p()∗ p ()U c. Any pair ( , c) solving c = U ∗ p()∗ p ()U c U ∗ p()∗ p()U
(12)
satisfies (left multiply by c∗ and use Cauchy–Schwarz) u | | p ()U p() u | | p ()
(13)
Here, plays the role of − . Therefore, to ensure a minimal residual norm, we are interested in the eigenpair of (12) with the smallest | |; we call this approach the linearized harmonic Rayleigh– Ritz method for polynomial eigenproblems. The word ‘linearized’ reflects the fact that we take the linear part of the Taylor series in (11). The vector u =U c is a linearized harmonic Ritz vector. Note that the linearized harmonic Ritz value satisfies (cf. (3)) = −
p() u 2 u ∗ p()∗ p () u
For the practical computation of the linearized harmonic Ritz pair, we proceed as follows. During the process, we compute the QR decomposition p()U = Q R incrementally (that is, in every step add an extra column to Q and R) and hence cheaply. Then, condition (iv) is equivalent to the low-dimensional projected generalized eigenproblem Q ∗ p ()U c = −1 R c Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
HARMONIC AND REFINED RAYLEIGH–RITZ FOR THE PEP
43
where we are interested in the maximal | −1 |; see [2, p. 294] for a similar formulation for the standard eigenvalue problem. As the harmonic Ritz value may be a dissatisfactory approximation to the sought eigenvalue (see [3] for the standard eigenvalue problem), we may subsequently determine a new approximate eigenvalue from the derived linearized harmonic Ritz vector; see [13] for a number of possible alternatives to do this. However, in the derivation of (12) we have neglected the second-order term involving F. Reintroducing this term in characterization (iii) above, we obtain p() u −(− ) p () u − F u⊥ p()U, and this is exactly the Galerkin condition p( ) u ⊥ p()U
(14)
(cf. the two characterizations (iii) in Section 2) where we are interested in the closest to . We will call this the harmonic Rayleigh–Ritz method for polynomial eigenproblems. Both the linearized harmonic method (12) and the harmonic method (14) reduce to (4) and (6) in case of the standard and generalized eigenvalue problems, respectively. The following result renders a pleasing property of the harmonic method. Proposition 4.1 If (, x) is an eigenpair of p()x = 0 then it is also a harmonic Ritz pair with respect to the search space span(x). Proof This follows directly from substitution in (14).
Therefore, if an eigenvector is in the search space, the harmonic Rayleigh–Ritz method will find it—unless we are in an unlucky (but not serious) circumstance, see the remarks after Proposition 2.2. The linearized harmonic Rayleigh–Ritz method, however, will in general miss an exact eigenvector in the search space, as may easily be checked. On the other hand, linearized harmonic Rayleigh– Ritz comes with the upper bound (13), which the non-linearized version lacks. The question raises which of these two advantageous properties is more important in practice. Experiments in Section 7 show that the harmonic extraction is generally much more promising than its linearized variant, heuristically meaning that the advantage of Proposition 4.1 generally outweighs the importance of (13). Of course, we are interested in the quality of the approximate eigenpair. Denote a perturbation of the polynomial p() by p() := l Al +l−1 Al−1 +· · ·+A0 , then the backward error (, u) of an approximate eigenpair (, u) can be defined as (see Tisseur [14]) (, u) := min{ : ( p()+ p())u = 0, A j E j , j = 0, . . . ,l} where E j are error matrices; in practice, one often takes either E j = I (corresponding to absolute perturbations) or E j = A j (corresponding to relative perturbations). The backward error () of an approximate eigenvalue can be defined as () := min (, u) u=1
Then we have [14]
(, u) = r (, u)
l
j E j
j=0
Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
44
M. E. HOCHSTENBACH AND G. L. G. SLEIJPEN
and
() = min ( p())
l
j E j
j=0
The pseudospectrum for the PEP can be defined as in Tisseur and Higham [15] ( p) := {z ∈ C|(z)} Then in terms of the pseudospectrum ( p), we have ∈ () ( p) Hence, from (13) we obtain that the pair (, u ), where u is a linearized harmonic Ritz vector, has a backward error with respect to absolute perturbations of at most | | p () u /(1+|| · · ·+||l )| | p ()U /(1+|| · · ·+||l ) Also, the approximate eigenvalue has a backward error with respect to absolute perturbations of at most | | min ( p ()U )/(1+|| · · ·+||l ). 5. REFINED RAYLEIGH–RITZ Another idea is to generalize refined Rayleigh–Ritz, where, for a , one minimizes A u − u over all u ∈ U,
u = 1
This can be either a fixed target or the computed Ritz value in each step; the latter was advocated by Jia [16] in the context of the Arnoldi method. Generalizing this idea to the polynomial eigenproblem, we minimize p() u ,
u ∈ U,
u=1
(15)
where again may be a fixed target or a Ritz value. Computationally, this approach amounts to determining the smallest right singular vector c of the tall and thin n ×k matrix p()U . In line with refined Rayleigh–Ritz terminology, we call the minimizing vector u =U c a refined Ritz vector. Having this vector, we can determine an approximate eigenvalue along the lines in [13]—as for the harmonic approach. Taking the target in (15) instead of the Rayleigh quotient is often more sensible in the beginning of the process and has the additional advantage that the QR decomposition of p()U can be computed incrementally; since p()U c = Q R c = R c in this case we only have to determine the smallest right singular vector of the k ×k upper triangular matrix R in the kth step of the process. This refined approach has the following equivalent characterizations: (i) u = argminu∈U,u=1 p()u, −2 where V = p()U and c − c ⊥ V, (ii) ( p() p()∗ )−1 V V −2 is maximal, Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
HARMONIC AND REFINED RAYLEIGH–RITZ FOR THE PEP
45
c = 2 c where 2 is minimal, (iii) U ∗ p()∗ p()U where u and c are related by u =U c. The next theorem is a generalization of part of [2, p. 290]. Theorem 5.1 For the residual of the refined Ritz vector, we have p() u
1 |−|+ p() sin(U, x) 1−sin2 (U, x)
where 1 is as in (10). Proof Decompose x = U xU + U eU , where xU :=UU ∗ x/UU ∗ x is the orthogonal projection of x onto U, xU = eU = 1, U = cos(U, x), and U = sin(U, x). Since p()xU = ( p()x − U p()eU )/U , we have by the definition of a refined Ritz vector and (9)
p() u p()xU 1 |−|+ U p() /U This theorem indicates a disadvantage of the refined approach: in order to have p() u → 0, we not only need sin(U, x) → 0 (the search space U should contain x), but also → (the target must converge to the wanted eigenvalue). Indeed, as can be checked, if x ∈ U but = , then the refined extraction will in general not select x as the best approximate eigenvector. The practical difficulty in taking a varying → is that it is computationally more expensive: we have to recompute p()U (and possibly its QR decomposition) whenever changes. Although this can be done relatively efficiently with a straightforward generalization of the approach presented in [17] for the case of two matrices, frequently varying would still amount to extra costs. Therefore, it could be a good idea to change the target only every now and then, for instance, change it to the Rayleigh quotient at a restart of the method if we are close enough to the eigenvalue (indicated by a small r ). At a restart, we start over with Unew ⊂ Uold with a basis of the form Unew :=Uold C, where Uold has a size n ×maxdim and C has orthonormal columns with size maxdim×mindim (see also Table II). In this case, we would have to recompute a QR decomposition of p()U C = Q RC in any case, hence this may be a relatively good moment to completely recompute p()U and its QR decomposition for a different . As an alternative, we can use the refined extraction in the beginning of the process and change to the harmonic extraction when converging; see also the numerical experiments in Section 7. We remark that the difficulty of the refined approach sketched above is also present in the refined approach for the standard and generalized eigenproblems; asymptotically, one has to change the target to ensure convergence to the wanted eigenpair.
6. SUBSPACE EXPANSION FOR THE POLYNOMIAL EIGENVALUE PROBLEM We take a new look at the Jacobi–Davidson subspace expansion for the polynomial eigenvalue problem (see [9, 11] for the previous work, and also [18]). In particular, we investigate alternative Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
46
M. E. HOCHSTENBACH AND G. L. G. SLEIJPEN
projections for the correction equation, and the convergence of the method when we solve the correction equations exactly or inexactly. Assume that we have an approximate eigenpair (, u), where the residual r = p()u is orthogonal to a certain test vector v. We are interested in an update s ⊥ u such that p()(u +s) = 0 that is, u +s is an eigenvector (although not normalized). Rewriting this equation in terms of the known approximate eigenvalue gives p()s = − p()u +( p()− p())u +( p()− p())s
(16)
We will neglect the third term on the right-hand side of (16), which is—under a mild assumption— of second order (O(s2 )) as is shown in the next lemma. Lemma 6.1 Let v be a test vector with r ⊥ v. If v ∗ p ()x = 0 then |−| = O(s). Proof This follows directly from v ∗ p()(u +s) = 0, v ∗ p()u = 0, v ∗ p ()x = 0, and (8).
We note that the condition v ∗ p ()x = 0 is not unnatural: if we take for v the left eigenvector y, then y ∗ p ()x = 0 implies that the condition number of the eigenvalue is infinite, see [14, Theorem 5]. In (16), now we would like to project out the term ( p()− p())u, rather than disregarding it, but the difficulty is that p()u is unknown. Therefore, we approximate the term by a multiple of a known quantity ( p()− p())u ≈ (−) p ()u and we ensure that we project out the factor p ()u. Actually, by doing this we disregard only second-order terms, which form the basis for a quadratically convergent method, see Proposition 6.2. We also wish to keep the information contained in the residual r = p()u. Since we assumed that r ⊥ v, the projection P = I − p ()uv ∗ /v ∗ p ()u satisfies our wishes; a possible correction equation is then p ()uv ∗ p()(I −uu ∗ )s = − p()u, I− ∗
v p ()u
s ⊥u
(17)
Because of the requirement r ⊥ v, the present in the right-hand side of this equation is related to the test vector v. For instance, if we choose v = u, then is equal to the Rayleigh quotient of u, the most appropriate root of u ∗ p()u = 0. We note that v = u is a logical choice, since in this case the operator in (17) maps from u ⊥ to u ⊥ , which makes it natural to repeat this operator in a Krylov setting for an inexact solve of the correction equation. For the in the left-hand side of (17), we may take the Rayleigh quotient, but also one of the three alternatives proposed in [13] (called two-dimensional Galerkin and one- and two-dimensional minres) that often seemed more favorable. In addition, it may be advantageous to replace the Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
HARMONIC AND REFINED RAYLEIGH–RITZ FOR THE PEP
47
left-hand side by the target for two different reasons: • in particular, in the beginning of the process, the target will often be more accurate than the Rayleigh quotient or any other of the approximations in [13]; • the computation of p ()u for a fixed may be a bit cheaper than that of p ()u for a varying , in particular in combination with the linearized harmonic approach of Section 4, where we already have to compute p ()U . To determine what ‘the beginning of the process’ is, we can monitor the residual norm. As long as r is larger than a certain parameter fix, we use the target in (17), after which we switch to a moving approximation ; see also Algorithm 1 in the next section. The following proposition states conditions under which the Jacobi–Davidson method, where we take v = u, has asymptotically quadratic convergence. Proposition 6.2 Suppose the Jacobi–Davidson method for the polynomial eigenvalue problem, where we solve the correction equation (17) exactly, converges to an eigenvalue with left and right eigenvectors y and x, respectively. If is simple, x ∗ p ()x = 0 and y ∗ p ()x = 0, then the method converges asymptotically quadratically. Proof Denote P = I − p ()uu ∗ /u ∗ p ()u While the true update s ⊥ u satisfies (cf. (16)) P p()Ps = −r + P( p()− p())u + P( p()− p())s
(18)
for the computed update s ⊥ u, we have P p()P s = −r (Note that compared with (17), we have replaced the projection I −uu ∗ by P, but since s ⊥ u and s ⊥ u, this is equivalent.) Therefore, P p()P(s − s ) = P( p()− p())u + P( p()− p())s Because of the assumption and Lemma 6.1, the last term is O(s2 ). For the second term, we have similar to (11) and using Lemma 6.1 P( p()− p())u = P Fu = O(|−|2 ) = O(s2 ) To make sure that s − s = O(s2 ), the last part of the proof is to show that the operator p ()x x ∗ p ()x x ∗ I− ∗
p() I − ∗
x p ()x x p ()x
(19)
is an invertible operator from x ⊥ to x ⊥ . Suppose therefore that this operator maps z ⊥ x to 0. Then it follows that p()z = p ()x for an ∈ C. Left multiplying by the left eigenvector gives 0 = y ∗ p()z = y ∗ p ()x. Because of the assumption, we must have = 0. Hence, p()z = 0 and Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
48
M. E. HOCHSTENBACH AND G. L. G. SLEIJPEN
since z ⊥ x and the assumption that is a simple eigenvalue, we have z = 0. Therefore, we have proved the injectivity of (19); the bijectivity follows from comparing dimensions. We remark that for a two-sided variant of Jacobi–Davidson (that is, the test vector v converges to the left eigenvector y), the condition x ∗ p ()x = 0 is no longer necessary. The following proposition proves what is often experienced in practice: inexact Jacobi–Davidson typically converges asymptotically linearly. By ‘inexact’ we mean that the correction equation is solved until the residual norm is reduced by a fixed factor. Proposition 6.3 We assume the same hypotheses as in Proposition 6.2, only now we solve the correction equation (17) inexactly, such that s ⊥ u satisfies P p()P s +r r < −1 ,
for <1. If where is the condition number of the operator in (19), seen as operator from x ⊥ to x ⊥ , the asymptotic convergence of the Jacobi–Davidson method is linear. Proof In this case, we have P p()P(s − s ) = 1 r f + P( p()− p())u + P( p()− p())s for a certain vector f ⊥ u, f = 1. Here, 1 is the precision with which the correction equation is solved and by the assumption that 01 . In the previous proposition, we saw that the last two terms on the right-hand side are O(s2 ), and that the operator P p()P is asymptotically invertible. Moreover, from (18) it is clear that, neglecting higher-order terms, r P p()Ps. Therefore, s − s s+ higher-order terms, where denotes the condition number of (19). Rather than a fixed residual reduction, we will take a fixed number of inner iterations to solve the correction equation (17) in the numerical experiments in the following section.
7. NUMERICAL EXPERIMENTS The following experiments were carried out in MATLAB. For all experiments, we first put the random ‘seed’ to 0 so that the results are reproducible. Experiment 7.1 To get some feeling for the different extractions, we first take 100×100 matrices A2 , A1 , and A0 with elements taken randomly from a uniform distribution over [0, 1]. Figure 1 shows the 200 eigenvalues. Also indicated in Figure 1 are the targets = −5 and −2.5. We build up a four-dimensional search space U to find the eigenpair corresponding to the eigenvalue = −2.69 . . . , which is the eigenvalue closest to both targets. The first basis vector of U is taken to be u 1 = x +w, where x is the corresponding eigenvector and w is a random vector. The other three basis vectors of U are selected randomly. For we take the values 10− j for j = 1, . . . , 5, meaning that the search space ranges from bad to good quality. Furthermore, the two different targets = −5 and −2.5 represent a not very accurate and a more accurate target, respectively. Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
49
HARMONIC AND REFINED RAYLEIGH–RITZ FOR THE PEP
Eigenvalues and targets 8 6 4
Imag(λ)
2 0 2 4 6 8 15
10
0
5 Real(λ)
5
Figure 1. The eigenvalues of the 100×100 random quadratic eigenvalue problem and targets = −5 and −2.5. Table I. Extraction results for 100×100 random matrices, targets = −5 and −2.5, and search spaces of different qualities. Target −5
−2.5
(U, x) Standard Linearized harmonic Harmonic Refined
3.2e−6 1.6e−5 6.1e−3 3.3e−6 4.8e−2
3.2e−5 1.6e−4 6.1e−3 3.3e−5 4.8e−2
3.2e−4 1.6e−3 6.1e−3 3.3e−4 4.8e−2
3.2e−3 1.5e−2 6.4e−3 3.3e−3 4.8e−2
3.2e−2 1.0e−1 3.3e−2 3.3e−2 5.8e−2
3.1e−1 4.4e−1 4.2e−1 3.4e−1 3.2e−1
Linearized harmonic Harmonic Refined
1.7e−4 3.3e−6 6.7e−3
1.7e−4 3.3e−5 6.7e−3
3.5e−4 3.3e−4 6.7e−3
3.3e−3 3.3e−3 7.5e−3
3.4e−2 3.4e−2 3.4e−2
1.4e−0 1.4e−0 3.2e−1
Table I gives the results of the four different extraction processes for = −5 and −2.5. We display (U, x) (this gives the best possible approximate vector in U) and (u, x), the angle of the approximate eigenvector with the exact eigenvector. It turns out that the results of the standard extraction are independent of the target ; the other extraction methods do depend on . For an inaccurate search space, say (U, x) ≈ 10−1 , the refined approach is the best, having a near-optimal extraction, which means (u, x) ≈ (U, x). For better search spaces, the refined approach does not improve any further, as already expected from the discussion after Theorem 5.1, and the harmonic and linearized harmonic approaches do the best job. For quite accurate search spaces, the harmonic approach is the best with an almost optimal extraction, with the standard extraction following in second place but with a clear difference. These results suggest to combine the strengths of the different extraction methods, giving the JDPOLY algorithm as outlined in Algorithm 1. Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
50
M. E. HOCHSTENBACH AND G. L. G. SLEIJPEN
Algorithm 1. Jacobi–Davidson for the polynomial eigenvalue problem Input: A device to compute A j x for arbitrary x, a starting vector u 1 , a target , a tolerance , and parameters threshold and fix Output: An approximate eigenpair (, u) with ≈ 1: s = u 1 2: for k = 1, 2, . . . do 3: rgs(Uk−1 , s) →Uk 4: Extract a Ritz pair (, c) close to : if (r threshold): use harmonic (or standard) extraction else use harmonic (or refined, linearized harmonic, standard) extraction, end if 5: u =Uk c 6: r = p() u 7: if (r ), stop, end if 8: if (r fix): z = p () u else z = p () u, end if
∗ 9: Solve (approximately) an s ⊥ u from I − uzu∗ z p()(I −uu ∗ ) s = −r 10: end for The ‘rgs’ in Line 3 stands for repeated Gram–Schmidt or any other numerical stable way to form an orthonormal basis for the search space. In Line 9, we have chosen v = u in the correction equation (17), corresponding to looking for an orthogonal update to an approximate eigenvector. Table II gives an oversight of some of the available parameters and the default value. Experiment 7.2 We test the JDPOLY algorithm for the above problem with target = −5 and the four different extraction methods. An inexact LU preconditioner for 2 A2 +A1 + A0 with drop tolerance 0.01 is used. Inspired by the previous experiment, we switch from the linearized harmonic and the refined extractions to the harmonic extraction if r threshold; we test various values for this parameter, see Table III. After extraction of an approximate eigenpair, all extraction methods except the standard approach employ the ‘two-dimensional Galerkin method’ [13] to determine a more accurate eigenvalue (for the standard extraction it turns out in practice that this extra step is generally unfavorable since a good quality vector is required). The harmonic approach takes much fewer iterations (20) than the standard extraction (47). The linearized harmonic and refined extractions in themselves do not converge in 100 outer iterations; indeed, this is what we expect for a fixed target as was predicted in Sections 4 and 5; using a fixed target they generally do not recognize an eigenvector that is present in the search space. However, if we combine them with the harmonic extraction, that is, switch to the harmonic extraction as soon as r
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
51
HARMONIC AND REFINED RAYLEIGH–RITZ FOR THE PEP
Table II. Parameters of the Jacobi–Davidson method for the polynomial eigenvalue problem with their default value. Parameter tol maxit extraction target mindim maxdim maxit inner inner tol fix u1 M1, M2 Mtype verbosity
Meaning
Default value
(Absolute) tolerance for the outer iteration Maximum number of outer iterations Extraction process Complex number of interest Dimension search spaces after restart Maximum dimension search spaces Maximum number of inner iterations Tolerance inner iteration Fix target until r fix Initial search space Preconditioner M = M1 M2 (possibly in factored form) Left or right preconditioning Output desired
10−6 1000 Harmonic Largest || 10 20 10 0 0.01 Random vector M=I Left No
Table III. Number of outer iterations and CPU time for a random 100×100 quadratic eigenvalue problem with target = −5 and various extraction methods. Extraction Standard Linearized harmonic Harmonic Refined
threshold
Iterations
Time
— 0.0 1.0 — 0.0 1.0 5.0
47 — 20 20 — 62 20
1.94 — 0.82 0.83 — 2.10 0.82
Experiment 7.3 Using the command sprand, we create random 1000×1000 matrices A2 , A1 , and A0 with density ≈ 10% and condition numbers = O(105 ). With target = 0 and an ILU preconditioner with drop tolerance = 0.001, the results of JDPOLY with the standard and harmonic extraction methods are summarized in Table IV. We experiment with three different numbers of inner iterations: 10, 5, and 0; in the last case we expand the search space by the preconditioned residual (no inner iterations). We see that the less accurately the correction equation is solved (which means that a good extraction process may get more important, in absence of a good expansion process), the larger the difference between the standard and harmonic extraction becomes. This experiment indicates that the harmonic extraction may be an important improvement if the quality of the search space expansion is modest, for instance if a (good) preconditioner is unavailable. Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
52
M. E. HOCHSTENBACH AND G. L. G. SLEIJPEN
Table IV. Number of outer iterations and CPU time for a random 1000×1000 quadratic eigenvalue problem with target = 0, various extraction methods, and three different numbers of inner iteration steps. maxit inner = 10
maxit inner = 5
maxit inner = 0
Extraction
Iterations
Time
Iterations
Time
Iterations
Time
Standard Harmonic
12 11
22.0 19.9
14 11
15.2 11.6
27 17
8.7 4.9
Experiment 7.4 Next, we consider an example arising from a damped gyroscopic system as in [19]: define m ×m tridiagonal matrices B2 = tridiag(1, 4, 1)/6,
B1 = tridiag(1, 0, −1)
B0 = tridiag(1, −2, 1),
C1 = tridiag(1, 2, 1)
where m = 90 and the 8100×8100 matrices A2 = c11 Im ⊗ B2 −c12 B2 ⊗ Im A1 = c21 Im ⊗ B1 −c22 B1 ⊗ Im +10−3 (c41 Im ⊗C1 −c42 C1 ⊗ Im ) A0 = c31 Im ⊗ B0 −c32 B0 ⊗ Im where c11 = 1, c12 = 1.3, c21 = 0.1, c22 = 1.1, c31 = 1, c32 = 1.2, c41 = 1.05, and c42 = 0.9. With target = 0, tol = 10−8 , and an ILU preconditioner ( = 0.001), the standard extraction did not converge to the required tolerance in 100 iterations; the harmonic, linearized harmonic, and refined extractions (the last two with threshold = 1) took 48, 43, and 49 steps, respectively. From this experiment, it seems that having search spaces of good quality, the harmonic extraction may be more accurate than the standard extraction, as was also suggested by Experiment 7.1. Experiment 7.5 Finally, we test with the utrecht-1331 matrix, a 1331×1331 quadratic eigenproblem, where A2 and A0 are symmetric positive definite and A1 is complex, singular, and non-Hermitian; cf., e.g. [18]. We try to compute the eigenvalue closest to target = −70 + 2000i, which is ≈ −73.33 + 2014i. With tol = 10−6 , maxit inner = 0 (i.e. taking the preconditioned residual) and an ILU preconditioner ( = 0.01), this eigenvalue is detected by the standard approach (21 iterations, 0.88 s), the harmonic approach (19 iterations, 0.87 s), and the linearized harmonic approach (19 iterations, 0.90 s); the refined approach did not converge in 100 outer iterations.
8. CONCLUSIONS We reviewed the harmonic Rayleigh–Ritz extraction for the standard and generalized eigenvalue problems, and discussed the problem of subspace extraction for the polynomial eigenvalue problem. While this paper focuses on how to extract an approximate vector from a search space, we refer to [13] for methods to derive an approximate eigenvalue from the approximate eigenvector. Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
HARMONIC AND REFINED RAYLEIGH–RITZ FOR THE PEP
53
We introduced harmonic Rayleigh–Ritz (two variants) and refined Rayleigh–Ritz for the polynomial eigenvalue problem. The harmonic approaches are slightly more expensive than the standard approach, but for interior eigenpairs in particular the (non-linearized) harmonic approach is theoretically more sound and numerically gives a better subspace extraction than the standard Rayleigh–Ritz method in many experiments. The refined approach may be worthwhile for a search space of poor quality, as is typical for the beginning of the process. To retain accuracy for the refined extraction towards the end of the process, we may have to let the target converge to the desired eigenvalue, for instance, by setting the target equal to the Rayleigh quotient when restarting, or by switching to the harmonic approach. The linearized harmonic extraction has the advantage that we have a bound (13) on the residual norm; on the other hand, an exact eigenpair is generally not a linearized harmonic pair. For the non-linearized extraction the situation is exactly the opposite; there is no direct upper bound for the residual, but an exact eigenpair satisfies (14). This last property may be considered important, and numerical experiments confirm that the (non-linearized) harmonic approach is often the most reliable. We embedded the subspace extraction techniques in a Jacobi–Davidson method, with resulting quadratic (with exact linear solves) or linear (with inexact linear solves) convergence and discussed various algorithmic details.
ACKNOWLEDGEMENTS
The authors thank the referees for very helpful and relevant comments. The research of the first author was supported in part by NSF grant DMS-0405387.
REFERENCES 1. Van der Vorst HA. Computational methods for large eigenvalue problems. Handbook of Numerical Analysis, vol. VIII. North-Holland: Amsterdam, 2002; 3–179. 2. Stewart GW. Matrix Algorithms, vol. II. SIAM: Philadelphia, PA, 2001. 3. Sleijpen GLG, Van der Vorst HA, Meijerink E. Efficient expansion of subspaces in the Jacobi–Davidson method for standard and generalized eigenproblems. Electronic Transactions on Numerical Analysis 1998; 7:75–89. 4. Van den Eshof J. Nested iteration methods for nonlinear matrix problems. Ph.D. Thesis, Utrecht University, 2003. 5. Paige CC, Parlett BN, Van der Vorst HA. Approximate solutions and eigenvalue bounds from Krylov subspaces. Numerical Linear Algebra with Applications 1995; 2(2):115–133. 6. Saad Y. Numerical Methods for Large Eigenvalue Problems. Manchester University Press: Manchester, U.K., 1992. 7. Parlett BN. The Symmetric Eigenvalue Problem. SIAM: Philadelphia, PA, 1998. 8. Jia Z. The convergence of harmonic Ritz values, harmonic Ritz vectors, and refined harmonic Ritz vectors. Mathematics of Computation 2005; 74(251):1441–1456. 9. Hochstenbach ME, Sleijpen GLG. Two-sided and alternating Jacobi–Davidson. Linear Algebra and its Applications 2003; 358(1–3):145–172. 10. Lanczos C. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. Journal of Research of the National Bureau of Standards 1950; 45(4):255–282. 11. Sleijpen GLG, Booten AGL, Fokkema DR, Van der Vorst HA. Jacobi–Davidson type methods for generalized eigenproblems and polynomial eigenproblems. BIT 1996; 36(3):595–633. 12. Stathopoulos A. A case for a biorthogonal Jacobi–Davidson method: restarting and correction equation. SIAM Journal on Matrix Analysis and Applications 2002; 24(1):238–259. 13. Hochstenbach ME, Van der Vorst HA. Alternatives to the Rayleigh quotient for the quadratic eigenvalue problem. SIAM Journal on Scientific Computing 2003; 25(2):591–603. Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
54
M. E. HOCHSTENBACH AND G. L. G. SLEIJPEN
14. Tisseur F. Backward error and condition of polynomial eigenvalue problems. Linear Algebra and its Applications 2000; 309(1–3):339–361. 15. Tisseur F, Higham NJ. Structured pseudospectra for polynomial eigenvalue problems, with applications. SIAM Journal on Matrix Analysis and Applications 2001; 23(1):187–208. 16. Jia Z. Refined iterative algorithms based on Arnoldi’s process for large unsymmetric eigenproblems. Linear Algebra and its Applications 1997; 259:1–23. 17. Spellucci P, Hartmann WM. A Q R decomposition for matrix pencils. BIT 2000; 40(1):183–189. 18. Hochstenbach ME, Notay Y. Homogeneous Jacobi–Davidson. CASA Report 06-36, Department of Mathematics, TU Eindhoven, The Netherlands, November 2006. Electronic Transactions on Numerical Analysis, in press. 19. Hwang T-M, Lin W-W, Mehrmann V. Numerical solution of quadratic eigenvalue problems with structurepreserving methods. SIAM Journal on Scientific Computing 2003; 24(4):1283–1302.
Copyright q
2008 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:35–54 DOI: 10.1002/nla
NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS Numer. Linear Algebra Appl. 2008; 15:55–82 Published online 19 December 2007 in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/nla.564
A time-independent approach for computing wave functions of the Schr¨odinger–Poisson system C.-S. Chien1, ∗, † , B.-W. Jeng2 and Z.-C. Li3,4 1 Department
of Applied Mathematics, National Chung-Hsing University, Taichung 402, Taiwan of Mathematics Education, National Taichung University, Taichung 403, Taiwan 3 Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung 804, Taiwan 4 Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 804, Taiwan 2 Department
SUMMARY We describe a two-grid finite element discretization scheme for computing wave functions of the Schr¨odinger–Poisson (SP) system. To begin with, we compute the first k eigenpairs of the Schr¨odinger– Poisson eigenvalue (ESP) problem on the coarse grid using a continuation algorithm, where the nonlinear Poisson equation is solved iteratively. We use the k eigenpairs obtained on the coarse grid as initial guesses for computing their counterparts of the ESP on the fine grid. The wave functions of the SP system can be easily obtained using the formula of separation of variables. The proposed algorithm has the following advantages. (i) The initial approximate eigenpairs used in the fine grid can be obtained with low computational cost. (ii) It is unnecessary to discretize the partial derivative of the wave function with respect to the time variable in the SP system. (iii) The major computational difficulties such as closely clustered eigenvalues that occur in the SP system can be effectively computed. Numerical results on the ESP and the SP system are reported. In particular, the rate of convergence of the proposed algorithm is O(h 4 ). Copyright q 2007 John Wiley & Sons, Ltd. Received 12 December 2006; Revised 22 October 2007; Accepted 22 October 2007 KEY WORDS:
Schr¨odinger–Poisson system; wave functions; finite element methods; two-grid scheme
1. INTRODUCTION During the past years, multiscale algorithms have become one of the most important research areas in scientific computation and have attracted the attention of researchers in computational physics, ∗ Correspondence
to: C.-S. Chien, Department of Applied Mathematics, National Chung-Hsing University, Taichung 402, Taiwan. † E-mail: [email protected] Contract/grant sponsor: National Science Council of R.O.C. (Taiwan); contract/grant number: NSC 95-2115-M-005004-MY3
Copyright q
2007 John Wiley & Sons, Ltd.
56
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
computational chemistry, engineering as well as in applied mathematics, see e.g. References [1, 2] for details. In this paper, we are concerned with the eigensolutions of the self-consistent Schr¨odinger–Poisson (SP) system, which is governed by )m i*t m = − 12 m +(W + W −∇ ·((∇W )∇W ) = n −n
∗
(2)
(∇W ) = 0 +1 |∇W |2 , n(x, t) =
∞
(1)
0 , 1 >0
m |m (x, t)|2
(3) (4)
m=1
with initial conditions m (x, 0) = 0m (x)
(5)
and periodic boundary conditions on the unit square = [0, 1]2 , m (x +ei , t) = m (x, t),
m = 0, 1, 2, . . .
(6)
Here, ei is the ith standard unit vector in R2 , m ’s are the occurrence probability of the initial states are given time-independent 1-periodic functions describing a dopant density and 0m (x), n ∗ and W effective exterior linear potential, and W is the self-consistent electric potential that satisfies the nonlinear Poisson equation (2). The nonlinearity in (2) is modeling a field-dependent dielectric constant, where n = ||2 is the charge density arising from the Schr¨odinger wave function . Equations (1)–(6) describe a quantum mechanical model of extremely small devices in semiconductor nanostructures where the quantum structure has to be taken into account. We assume that the normalization |0m (x)|2 dx = 1, m = 0, 1, 2, . . . (7)
and the condition
W (x, t) dx = 0
(8)
hold for the system. We also impose charge neutrality, i.e. (n −n ∗ ) dx = 0
(9)
Illner et al. [3] showed that the SP system has the following stationary states: m (x, t) = e−im t m (x),
m = 1, 2, 3, . . .
(10)
where m ∈ R and m (x) are real time-independent wave functions. Ringhofer and Soler [4] proposed to use the Crank–Nicklson method for computing wave functions of the SP system, where both mass and energy of the system are preserved. However, there is no numerical report Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
57
therein. In this paper, we wish to give a different approach for computing wave functions of the SP system. Inserting (10) into the SP system, one obtains )−m ]m = 0 − 12 m +[(W + W
(11)
−∇ ·(0 +1 |∇W |2 )∇W = n −n ∗ |m (x)|2 dx = 1
(12) (13)
W (x) dx = 0
(14)
2 where n = n(x) = ∞ odinger– m=1 m |m (x)| . Equations (11)–(14) are called the nonlinear Schr¨ Poisson eigenvalue (ESP) problem. It has been indicated in Reference [3] that there are infinite solutions (m , ±m ) to the ESP in the weak sense. Recently, Chang et al. [5] described a timeindependent continuation algorithm for computing wave functions of a nonlinear Schr¨odinger equation: i*t = −+ W (x)+||2 , (x, t) = 0,
t>0, x ∈ 1 ⊆ R2
x ∈ *1 , t0
(15)
where (x, t) is the wave function, W (x) = 12 (21 x12 +22 x22 ) is the trapping potential with 21 22 , and is the unit disk in R2 . By neglecting the subscript m in (10) and inserting it into (15), we obtain a nonlinear eigenvalue problem: −(x)+ W (x)(x)+3 (x) = (x) in (x) = 0
on *
(16)
Equation (16) can be solved using numerical continuation methods, where the parameter is treated as the continuation parameter. The wave function (x, t) = e−it (x) of (16) can be easily obtained whenever a solution curve, say the solution curve branching from the first bifurcation, is numerically traced. The numerical algorithm we propose in this paper for computing the eigenpairs of the SP system is different from those that are commonly used in the literatures, e.g. the numerical methods described in Reference [4]. We observe that algorithms for solving the ESP and (16) are different. However, we can use the same idea to compute wave functions of the SP system whenever the eigenpairs of the ESP are obtained. Our aim here is to develop two-grid finite element discretization schemes for computing the first few eigenpairs of the SP system. The two-grid method was first proposed by Xu [6] for solving semilinear elliptic equations. Here, one first solves the partial differential equation (PDE) on a coarse grid to obtain a rough approximate solution. Next, one solves a linear approximation of the PDE on a fine grid to improve and to obtain a better approximate solution. The final approximate solution is obtained by solving a quadratic approximation of the PDE on the same coarse grid as above. Chien and Jeng [7] exploited the two-grid method of Xu [6] to develop a two-grid discretization scheme for semilinear elliptic eigenvalue problems. In Reference [8] Xu and Zhou developed a two-grid discretization scheme for computing the first few eigenpairs of linear eigenvalue problems. The difference between the two-grid discretization schemes in Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
58
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
References [6, 8] is that in the latter one makes a further correction for the computed eigenpairs using Rayleigh quotient iteration (RQI) on the fine grid. This is because the second derivative in the quadratic approximation for the linear eigenvalue problem is zero. Recently, Chang et al. [9] described a two-grid centered difference discretization scheme for computing the first few eigenpairs of the ESP, where the nonlinear term (∇W ) in (2) is set to be 1. Other numerical methods for computing the first few eigenpairs of the ESP can be found, e.g. in Reference [10]. In this paper we consider the more general SP system than those given in References [9, 10] where (1) and the nonlinear term in (2) are taken into account. It is evident that the nonlinear Poisson equation (2) should be solved in an iterative way. Instead of discretizing the left-hand side of (1) directly, we will solve the ESP as in Reference [9], where the Laplacian will be discretized by the second-order triangular elements. To compute the first few eigenpairs of the SP system, first we have to deal with eigenpairs of the Sch¨odinger eigenvalue (SE) problem: −u + f u = u
in = [0, 1]2
(17)
with periodic boundary conditions on *. In References [11, 12], Schepper studied finite element methods for a class of second-order linear elliptic eigenvalue problems on a rectangular domain with mixed classical and (semi-) periodic boundary conditions. The class includes (17) as a special case. However, in order to be consistent with the practical situation in quantum mechanics, one must impose periodic boundary conditions on (17). This paper is organized as follows. In Section 2 we establish the finite element theory for the SP system. We choose a proper subspace V of the Sobolev space H 1 () as the space of test functions to obtain a suitable variational formulation for the linear elliptic eigenvalue problem with periodic boundary conditions. We indicate that this variational formulation is basically equivalent to the classical differential eigenvalue problem. Moreover, this variational formulation can be considered as the general framework of abstract elliptic eigenvalue problems for symmetric, bounded, and coercive bilinear forms in Hilbert space. In Section 3 we construct a suitable finite element approximation subspace Vh of the space V . We describe a two-grid finite element discretization scheme for computing the first few eigenpairs of the SE problem in Section 4. A two-grid finite element discretization scheme is proposed for computing the first few eigenpairs of the ESP, where the nonlinear Poisson equation (2) is solved iteratively. As far as the first few eigenpairs of the ESP are obtained, the wave functions of the SP system can be computed using (10). Our numerical results are reported in Section 5, where the test problems include both the ESP and the SP system. In particular, we show that the convergence rate of the proposed algorithm for computing the second eigenpair of the linear eigenvalue problem is O(h 4 ), which is a significant improvement to the one given in Reference [9] that has only O(h 2 ) convergence rate. Finally, some concluding remarks are given in Section 6.
2. BASIC FINITE ELEMENT THEORY 2.1. Variational formulation and equivalence Consider the following second-order elliptic eigenvalue problem: 2 * *u ai j +a0 u = u in = (0, 1)2 − *x *x i j i, j=1 Copyright q
2007 John Wiley & Sons, Ltd.
(18)
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
59
with periodic boundary conditions u(x1 , 0) = u(x1 , 1),
0x1 1
*u *u (x1 , 0) = − (x1 , 1), *n a *n a u(0, x2 ) = u(1, x2 ),
(19)
0x1 1
(20)
0x2 1
*u *u (0, x2 ) = − (1, x2 ), *n a *n a
(21)
0x2 1
(22)
where *u/*n a ≡ i,2 j=1 ai j (*u/*x j )n i is the conormal derivative of u associated with the matrix (ai j ), and n = (n 1 , n 2 ) is the outward unit normal vector to *. Suppose that the functions ai j (x) and a0 (x) satisfy the usual symmetry and ellipticity conditions: ai j (x) ∈ L ∞ (), ∃>0
s.t.
2 i, j=1
i, j = 1, 2
ai j (x) i j ( 21 + 22 )
(23)
∀ 1 , 2 ∈ R
a.e. in
a12 (x) = a21 (x) a.e. in a0 (x) ∈ L ∞ ();
(24) (25)
∃c0 >0 s.t. a0 (x)c0
a.e. in
(26)
Let 1 = {(x1 , 0) : 0x1 1}, 2 = {(0, x2 ) : 0x2 1}, 3 = {(x1 , 1) : 0x1 1}, and 4 = {(1, x2 ) : 0x2 1} be the four sides of and * = 1 ∪2 ∪3 ∪4 . Let be the usual trace operator, i.e. : v ∈ H 1 () −→ v ∈ L 2 (*) be a continuous linear mapping such that v = v|* . Note that since v is continuous, its restriction to * is a continuous function on *. Thus, if ⊂ R2 , the graph of v|* can be drawn as a continuous curve above *. We choose V = {v ∈ H 1 () : v|1 = v|3 , v|2 = v|4 }
(27)
as the space of test functions. Then the corresponding variational or weak formulation to the problem (18)–(22) is Find (u, ) ∈ V ×R such that a(u, v) = (u, v) L 2 () ∀v ∈ V
(28)
where a(u, v) =
*u *v ai j +a0 uv dx *x j *xi i, j=1 2
and
(u, v) L 2 () =
uv dx
(29)
Theorem 2.1 Let (u, ) ∈ C 2 ()×R solve (18) with boundary conditions (19)–(22). Then (u, ) is a solution to the variational problem (28). Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
60
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
Proof Let (u, ) ∈ C 2 ()×R satisfy (18) with boundary conditions (19)–(22) and let v ∈ V . Then Green’s formula yields (u, v) L 2 () = uv dx = uv dx
=
2
* − i, j=1 *x i
*u ai j +a0 u v dx *x j
2
*u *v = ai j dx − *x j *xi i, j=1 =
*u v ds + * *n a
a0 uv dx
*u *v ai j +a0 uv dx *x j *xi i, j=1 2
= a(u, v)
Note that the boundary term ‘ * (*u/*n a )v ds’ vanishes for v ∈ V because v |1 = v |3 , v |2 = v |4 , *u/*n a |1 = −*u/*n a |3 , and *u/*n a |2 = −*u/*n a |4 . Thus, (u, ) is also the solution to the variational problem (28). Next, by following the arguments in Hall and Porsching [13] we will prove the companion result, namely, that a solution to the variational problem (28) solves the classical eigenvalue problem (18)–(22). Theorem 2.2 Let (u, ) ∈ V ×R solve the variational problem (28) and suppose that u ∈ C 2 () and *u/*n ∈ C(*). Then (u, ) solves the eigenvalue problem (18) with boundary conditions (19)–(22). Proof Suppose that (u, ) satisfies the variational problem (28) and u ∈ H 1 (). From (28) and Green’s formula, we have 2 2 * *u *u *v *u ai j +a0 u v dx = − ai j dx − v ds + a0 uv dx *x j *x j *xi i, j=1 * *n a i, j=1 *x i
*u v ds * *n a *u = (u, v) L 2 () − v ds * *n a *u = uv dx − v ds ∀v ∈ V * *n a
= a(u, v)−
Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
61
Thus, we obtain the following equation:
2
* − i, j=1 *x i
*u *u v ds = 0 ai j +a0 u −u v dx + *x j * *n a
∀v ∈ V
(30)
Since v is arbitrary, we obtain
2
* − i, j=1 *x i
*u ai j +a0 u −u v dx = 0 *x j
∀v ∈ C 1 ()
(31)
and
*u v ds = 0 ∀v ∈ V * *n a
(32)
Also since v is arbitrary in C 1 (), the integrand of (31) must be zero, i.e. 2
* − i, j=1 *x i
*u ai j +a0 u = u *x j
in
(33)
Below, let us prove (33). The cutoff function is defined as
(x) =
e1/(|x| 0
2 −1)
for |x|<1 for |x|1
The nth derivative of (x) is
(n) (x) =
Pn (x) (x) (1−|x|2 )n
where Pn (x) is a polynomial of degree n. Note that Pn (x) is continuous and bounded, see Brenner and Scott [14, p. 26]. Now we use (31) to show that (33) holds by contradiction. Suppose that 2
* g =− i, j=1 *x i
*u ai j +a0 u −u = 0 *x j
at (x0 , y0 ) ∈
Without loss of generality, we assume gg0 >0 in the neighborhood of (x0 , y0 ): R (x0 , y0 ) = {(x, y)|(x − x0 )2 +(y − y0 )2 < } Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
62
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
due to the property of continuous functions. We design a specific function v=
e1/((
x−x0 2 y−y0 2 ) +( ) −1)
, x ∈ R (x0 , y0 )
0
otherwise
Obviously, v ∈ C 1 (S), then
g v ds
R (x0 ,y0 )
g0 v dsg0
R (x0 ,y0 )
v ds
g0 >0 where >0. This contradicts (31). Next, we obtain from (32) 1 ∪3
*u v ds = *n a
1
v(x1 , 0)
0
*u *u (x1 , 0)+ (x1 , 1) dx1 = 0 *n a *n a
∀v ∈ V, v|2 = v|4 = 0
1 *u *u *u v ds = v(0, x2 ) (0, x2 )+ (1, x2 ) dx2 = 0 *n a *n a 2 ∪4 *n a 0 ∀v ∈ V, v|1 = v|3 = 0
(34)
(35)
Also since v ∈ H 1/2 (*) (due to v ∈ H 1 ()) is arbitrary, and the cutoff function in one dimension, v ∈ H 1/2 (*), based on the above arguments, we obtain from (34) and (35) *u *u (x1 , 0) = − (x1 , 1), *n a *n a
0x1 1
*u *u (0, x2 ) = − (1, x2 ), *n a *n a
0x2 1
which are the boundary conditions (20) and (22). The boundary conditions (19) and (21) follow since u ∈ V . Therefore, (u, ) satisfies (18) with boundary conditions (19)–(22). From Theorems 2.1 and 2.2 we have that the eigenvalue problem (18)–(22) and the variational problem (28) are basically equivalent. 2.2. Existence of eigenpairs of the variational problem We will show that the bilinear form a(·, ·) and the space V defined in (29) and (27), respectively, satisfy some important properties. In what follows the notations · m, and |·|m, denote the Sobolev norm and seminorm in the mth order Sobolev space H m () = W m,2 (), m ∈ N∪{0}, respectively. Note that H 0 () = L 2 () and u 0, = |u|0, = u L 2 () . Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
63
Proposition 2.3 The assumptions (23)–(26) imply that the bilinear form a(·, ·) defined in (29) is symmetric, bounded, and coercive on V × V . Proposition 2.4 The space V = {v ∈ H 1 () : v|1 = v|3 , v|2 = v|4 } defined in (27) is dense and compactly imbedded in L 2 (). Moreover, it forms a closed subspace of H 1 (). From Propositions 2.3 and 2.4 we may consider the variational problem (28) in the general framework of abstract elliptic EVPs in Hilbert spaces. In order to study the existence of eigenpairs of the variational problem (28), it is useful to introduce the linear operator T : L 2 () −→ V defined by T f ∈ V,
a(T f, v) = ( f, v) L 2 ()
∀v ∈ V
(36)
See References [15, p. 671; 16, Section 6.2]. Then T is the solution operator for the boundary value problem: 2
* L(u) := − i, j=1 *x i
*u ai j +a0 u = f *x j
in
(37)
with periodic boundary conditions (19)–(22), i.e. u = T f solves (37) with periodic boundary conditions (19)–(22). Thus, T is the inverse of the differential operator L, considered on functions that satisfy the boundary conditions (19)–(22). Note that if f ∈ L 2 (), then the linear form v −→ (v) = ( f, v) L 2 () is bounded (or continuous) on V , i.e. ∃c>0
s.t. |(v)|c v 1,
∀v ∈ V
Since the bilinear form a(·, ·) : V × V −→ R is symmetric, bounded, and coercive on V × V and the linear functional (·) : V −→ R is bounded on V , the Lax–Milgram theorem shows that Equation (36) has a unique solution T f for each f ∈ L 2 (). Moreover, since T f 21, a(T f, T f ) = ( f, T f ) L 2 () f L 2 () T f L 2 () f L 2 () T f 1, we have that 1
T f 1, f L 2 ()
∀ f ∈ L 2 ()
(38)
where >0 is the coercivity constant of a(·, ·). Further, the linear operator T has the following properties. Proposition 2.5 The solution operator T defined on V is compact, i.e. T (B) is precompact in V for every bounded subset B of V . Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
64
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
Proposition 2.6 T : V −→ V is a self-adjoint and positive operator on V with the inner product a(·, ·), that is, (i) self-adjoint: a(T u, v) = a(u, T v) for all u, v ∈ V , (ii) positive: a(T v, v)>0 for all 0 = v ∈ V . Now, the existence of exact eigenpairs for the variational problem (28) can be stated and proved as follows. Theorem 2.7 (i) The eigenvalues i (i = 1, 2, . . .) of the variational problem (28) form an increasing sequence 0<1 2 . . . m . . . −→ +∞ and each of the eigenvalues having a finite (geometric) multiplicity and being repeated a finite number of times is equal to its multiplicity. (ii) There exists an orthonormal basis for the space L 2 () formed from the eigenfunctions u i associated with the eigenvalues i , i.e. a(u i , v) = i (u i , v) L 2 () ,
∀v ∈ V
(u i , u j ) L 2 () = i j −1/2
(iii) Further, the function sequence {i the inner product a(·, ·).
u i } forms an orthonormal basis for the space V with
Proof The proof is quite standard, see e.g. Reference [15], and is omitted here.
Now we are ready to state a density property of the space V defined in (27), which is crucial to obtain the convergence of the finite element methods. The proof is a slight modification of the one in Reference [12] and is omitted here. Theorem 2.8 H 2 ()∩ V is dense in V .
3. THE FINITE ELEMENT APPROXIMATION Let {Th }h be a family of triangulations of with identical triangular elements K , see Figure 1. With a triangulation Th and a fixed number k ∈ N, we associate the standard function spaces X h = {v ∈ C 0 () : v| K ∈ Pk (K ) ∀K ∈ Th } ⊂ H 1 () X 0h = {v ∈ X h : v = 0 on *} ⊂ H01 () N where Pk (K ) stands for the set of polynomials on K of degree k in each variable. Let {ai,h }i=1 be the usual set of all nodes associated with Th , where N ≡ N (h) denotes their total number.
Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
(r _1)c +2
• (r _2)c+1 • • • Γ • • 2c+1 • c+1 • •1
(r _1)c+1
2
• • • • • • • • • 2
• • • • • • • • • 3
• • • • • • • • •
Γ3
• • • • • • • • •
• • • • • • • • •
• • • • • • • • •
Γ1
rc _1
• • • • • • • • • c _1
65
• rc • (r _1)c • • • Γ • • 3c • 2c • 4
c
Figure 1. A triangulation of and the numbering of the nodes (case k = 2).
In each element they are chosen in an identical way, according to the triangle of type k, see References [14, Section 3.2; 17, pp. 47–55]. Hence, the nodes will form a rectangular array, say with r rows and c columns. The numbering of the nodes is shown in Figure 1 (case k = 2). N be the canonical basis of X corresponding to the nodes {a } N . To construct a Let { i,h }i=1 h i,h i=1 suitable subspace of the space V , we introduce the following linear combinations of the basis functions i,h : vert i,h = i,h + (r −1)c+i,h ,
hor jc+1,h = jc+1,h + ( j+1)c,h ,
i = 2, . . . , c −1 j = 1, . . . ,r −2
(39)
orig
1,h = 1,h + c,h + (r −1)c+1,h + r c,h From the above discussion, we have the following proposition. Proposition 3.1 The space Vh defined by orig
vert Vh = X 0h ⊕span{i,h : i = 2, . . . , c −1}⊕span{hor jc+1,h : j = 1, . . . ,r −2}⊕span{1,h }
(40)
= (r −1)(c −1). is a finite dimensional subspace of V with dimension N Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
66
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
For simplicity, we will omit the subscript h when no confusion is possible. The following result is important for the error analysis. Proposition 3.2 The space Vh shows the standard approximation property: there exists a constant C>0 independent of h such that inf {|v −vh |0, +h|v −vh |1, }Ch s+1 v s+1,
vh ∈Vh
∀v ∈ V ∩ H s+1 (), 1sk
(41)
Proof Consider v ∈ V ∩ H s+1 (). Let h v ∈ X h be the usual piecewise Lagrange interpolant of v with respect to the FE-mesh, i.e. let h v =
r −1 c
v(a jc+i ) jc+i
j=0 i=1
Since v ∈ V satisfies the boundary conditions v|1 = v|3 and v|2 = v|4 , we have that v(ai ) = v(a(r −1)c+i ), v(a jc+1 ) = v(a( j+1)c ),
i = 2, . . . , c −1 j = 1, . . . ,r −2
v(a1 ) = v(ac ) = v(a(r −1)c+1 ) = v(ar c ) Then from (39) and the direct sum (40), we obtain h v =
r −2 c−1
v(a jc+i ) jc+i +
j=1 i=2
+
r −2 j=1
c−1 i=2
v(ai )[ i + (r −1)c+i ]
v(a jc+1 )[ jc+1 + ( j+1)c ]+v(a1 )[ 1 + c + (r −1)c+1 + r c ] ∈ Vh
By the classical interpolation error estimates that have been established in Reference [17, Section 3.1], we have that |v −h v|0, Ch s+1 |v|s+1,
and |v −h v|1, Ch s |v|s+1,
Thus, inf {|v −vh |0, +h|v −vh |1, } |v −h v|0, +h|v −h v|1,
vh ∈Vh
Ch s+1 |v|s+1, Ch s+1 v s+1,
Now, the finite element approximation of the variational problem (28) is as follows: Find (u h , h ) ∈ Vh ×R such that a(u h , vh ) = h (u h , vh ) L 2 () Copyright q
2007 John Wiley & Sons, Ltd.
∀vh ∈ Vh
(42)
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
(r _2)(c _1)+1 (r _ 3)(c _1)+1
2(c _1)+1 (c _1)+1
• • • • • •
• • (r _1)(c _1) • • (r _2)(c _1)
• • 3(c _1) • • 2(c _1) • • c _2 c _1
• • • • • • •1 • • 2
67
3
Figure 2. Renumbering of the nodes not belonging to 3 or 4 .
where a(·, ·) is given by (29). For this variational approximation problem (42), a discrete analogue of Theorem 2.7 holds. Theorem 3.3 Problem (42) has a finite sequence of eigenvalues 0<1,h 2,h · · · N ,h ,
= dim Vh N
and corresponding eigenfunctions u 1,h , u 2,h , . . . , u N ,h ∈ Vh , which can be chosen to satisfy a(u i,h , vh ) = i,h (u i,h , vh ) L 2 ()
∀vh ∈ Vh
(u i,h , u j,h ) L 2 () = i j
In order to solve for (u h , h ), we first renumber the nodes that do not belong to 3 or 4 as shown in Figure 2, and let the basis functions 1 , 2 , . . . , N of Vh be orig
1 = 1
i = ivert ,
Copyright q
i = 2, . . . , c −1
(43)
j (c−1)+1 = hor jc+1 ,
j = 1, . . . ,r −2
j (c−1)+i = jc+i ,
j = 1, . . . ,r −2, i = 2, . . . , c −1
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
68
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI orig
where the functions ivert , hor are given by (39). Then u h , vh ∈ Vh can be expressed jc+1 , and 1 , i.e. as the linear combinations of the basis functions i , i = 1, 2, . . . , N uh =
N
ci i
and vh =
i=1
N
djj
(44)
j=1
Substitution of (44) into (42) and use of the fact that a(·, ·) and (·, ·) L 2 () are bilinear lead to the equation N N
a(i , j )ci d j = h
i=1 j=1
(i , j ) L 2 () ci d j
i=1 j=1
or, more concisely, N
N N
dj
j=1
N
K i j ci −h
i=1
N
Mi j ci = 0
(45)
i=1
where K i j = a(i , j ) and Mi j = (i , j ) L 2 () . Note that matrices K i j and Mi j can be evaluated , are known functions. Since vh is arbitrary, so are the coefficients d j ; this since i , i = 1, 2, . . . , N implies that (45) holds only if N
K i j ci = h
i=1
N
Mi j ci ,
j = 1, 2, . . . N
i=1
or, more compactly, K ch = h Mch
(46)
× N symmetric positivewhere ch = [c1 , . . . , c N ]T ∈ R N , and K = (K i j ) and M = (Mi j ) are N definite matrices with entries K i j and Mi j , respectively. Thus, the variational approximation problem (42) is reduced to solve the generalized eigenvalue problem (46). Once the eigenpairs (ch , h ) ∈ R N ×R of (46) are solved, the approximate eigenfunctions u h ∈ Vh can be found from the first equation of (44). Note that the method given above is equivalent to the direct constraint method [18, Section 4]. Besides the direct constraint, we can use the penalty technique [18, Section 7] to treat the periodic boundary conditions. More precisely, define another bilinear form 2 1 *u *v Pc a p (u, v) = ai j +a0 uv dx + [u(x1 , 0)−u(x1 , 1)] h *x j *xi 0 i, j=1 1
× [v(x1 , 0)−v(x1 , 1)] dx1 +
[u(0, x2 )−u(1, x2 )][v(0, x2 )−v(1, x2 )] dx2
0
where Pc and are positive constants, which are called the penalty constant and penalty power, respectively. Then the penalty method is designed to seek the approximate eigenpair (u h , h ) ∈ X h ×R such that a p (u h , vh ) = h (u h , vh ) L 2 () Copyright q
2007 John Wiley & Sons, Ltd.
∀vh ∈ X h Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
69
The convergence rate of the penalty method can be found in many literatures, see e.g. References [18–25]. The further discussion about the penalty method will be given elsewhere.
4. TWO-GRID DISCRETIZATION SCHEMES 4.1. The SE problem Since the SE problem −u + f u = u
in = (0, 1)2
(47)
is a special case of (18), we have to impose the periodic boundary conditions (19)–(22) on (47), namely, u(x1 , 0) = u(x1 , 1),
0x1 1
*u *u (x1 , 0) = − (x1 , 1), 0x1 1 *n *n u(0, x2 ) = u(1, x2 ), 0x2 1 *u *u (0, x2 ) = − (1, x2 ), *n *n
(48)
0x2 1
We remark here that two additional boundary conditions concerning normal derivatives are imposed on (48), which are different from the boundary conditions in Reference [9] using centered difference approximations. In (47) the function f is a 1-periodic function describing the effective exterior linear potential which satisfies f (x) ∈ L ∞ ();
∃c0 >0 s.t. f (x)c0 a.e. in
Actually, (47) is also a special case of the well-known Kohn–Sham N -eigenfunction equation in condensed matter and quantum-chemistry computation: −n (r )+ f (r )n (r ) = n n (r ),
r ∈ R3 , n = 1 : N
(49)
where 2N is the number of electrons in the system, or their number per period in the case that f (r ) is a periodic function as we consider here. Note that N can be very large, see e.g. References [1, 2] and references cited therein. The variational formulation of problem (47) with boundary conditions (48) is Find (u, ) ∈ V ×R such that as (u, v) = (u, v) L 2 ()
∀v ∈ V
where the space V is defined by (27) and as (u, v) = (∇u ·∇v + f uv) dx
(50)
(51)
The corresponding finite element approximation to the variational problem (50) is Find (u h , h ) ∈ Vh ×R such that as (u h , vh ) = h (u h , vh ) L 2 () Copyright q
2007 John Wiley & Sons, Ltd.
∀vh ∈ Vh
(52)
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
70
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
where the finite dimensional subspace Vh of V is given by (40). Note that the model (47)–(48) is a special case of the eigenvalue problem (18)–(22). Therefore, the discussions in Sections 2 and 3 also hold for the SE problem (47). Let h, h ∈ (0, 1) be chosen so that h = O( h 2 ). We divide the domain into two uniform triangulations T and T , and let V , V ⊂ V be the corresponding finite-dimensional subspaces, which h h h h are defined by (40). From the discussion in the above section, the finite element solutions on the coarse and fine grids to the SE problem (47) with (48) can be reduced to solve the following two generalized eigenvalue problems:
N h Find (c h , h ) ∈ R ×R such that K h c h = h M h c h
Find (ch , h ) ∈ R Nh ×R such that K h ch = h Mh ch
(53) (54)
× N N h h , and K h , Mh ∈ R Nh × Nh . In order to derive the where N h = dim V h , Nh = dim Vh , K h , M h ∈R two-grid scheme, we treat the generalized eigenvalue problems (53) and (54) as two nonlinear systems of equations:
F h (x, ) = (K h −M h )x = 0
(55)
Fh (x, ) = (K h −Mh )x = 0
(56)
and
N N h h and Fh : R Nh ×R → R Nh . We will discuss how the extremum eigenpairs where F h : R ×R → R h be the on the fine grid can be approximated by their counterparts on the coarse grid. Let I h
interpolation operator from the coarse space R Nh to the fine space R Nh . We have the following result. The proof is a slight modification given in Reference [9] and is omitted here. Theorem 4.1 Assume that (c h , h ) satisfies F h (c h , h ) = 0 and (ch , h ) is the zero point of Fh (x, ) = 0 on the fine grid. Then the approximate eigenvector c¯h on the fine grid is obtained by solving h K h c¯h = ch ) h Mh (I h
(57)
h : R N h → R Nh is the interpolation operator defined above. where I h
Note that Davidson’s method [26] has been reported to be quite successful for computing the lowest eigenvalues and their corresponding eigenvectors of symmetric eigenvalue problems in quantum chemistry. Davidson’s method is regarded as an extension of the Lanczos method, and from the viewpoint of numerical implementation it is more related to Arnoldi’s method [27]. In Reference [28], Sleijpen and van der Vorst combined Jacobi’s method with Davidson’s method called the Jacobi–Davidson method, which can efficiently improve the convergence rate of Davidson’s method and can be modified to compute nonextremal eigenvalues. Moreover, it can also be applied to solve generalized eigenproblems and polynomial eigenproblems [29]. However, a detailed implementation of the Jacobi–Davidson method for solving the SP system is beyond the scope of this paper and will be given elsewhere. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
71
Suppose that we already obtained the eigenpair on the coarse grid. Then the fine grid approximate eigenvector c¯h can be obtained by solving the linear system (57). To obtain the fine grid approximate eigenvalue ¯ h , we compute the Rayleigh quotient: c¯T K h c¯h ¯ h = Th c¯h Mh c¯h Actually the approximate eigenpair (c¯h , ¯ h ) is still not accurate enough. We use (c¯h , ¯ h ) as the initial point and perform the RQI to improve the accuracy of the eigenpair. Since the fine grid solution (c¯h , ¯ h ) serves only as starting initial guess for the RQI, it is unnecessary to compute the approximate eigenvector c¯h on the fine grid to the desired accuracy for solving the linear system (57). Thus, we propose to use the iterative method, e.g. CG method, MINRES, etc., to solve (57) only a few iterations. Suppose that (x1 , 1 ) is an eigenpair of the generalized eigenvalue problem K x = M x, and (x0 , 0 ) is an approximation to (x1 , 1 ). In the RQI, to obtain a better estimate of the eigenvector, we solve the following linear system: (K −0 M)z = M x0
(58)
However, this system is ill-conditioned as the approximate eigenvalue 0 is close to the exact one 1 . Instead of solving (58), we use the idea of Lui and Golub [30] to solve a rank-one modification of the coefficient matrix K −0 M, i.e. (K −0 M +(M x0 )(M x0 )T )y = M x0
(59)
Then we have (K −0 M)y = (1−(M x0 )T y)M x0 Thus, the solution of (58) is z = y/(1−(M x0 )T y). Our numerical results show that the technique can be used to handle both simple and multiple eigenvalues. Note that linear systems with multiple right-hand sides that appear in the corrector step of Algorithm 4.2 below can be effectively solved using the conjugate gradient method in Reference [31] or the MINRES in Reference [32]. The two-grid finite element discretization scheme for the SE problem (47) with boundary condition (48) is described as follows. Algorithm 4.2 A two-grid finite element discretization algorithm for computing the extremum eigenpairs of the SE problem (47) with periodic boundary conditions (48). Input := stopping criterion for the RQI. 1 m 1. Predictor step: Find the first m eigenvalues , . . . , and the corresponding eigenvectors h h
1 , . . . , cm ∈ R N h with [(ci )T M(ci )]1/2 = 1, i = 1, . . . , m, on the coarse grid such that c h h h h h i i i K = Mh c , h c h h h
Copyright q
2007 John Wiley & Sons, Ltd.
i = 1, 2, . . . , m Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
72
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
2. Corrector step: (i) Perform a few iterations of the CG method or the MINRES for each SPD linear system on the fine grid: Find ch1 , . . . , chm ∈ R Nh such that i i K h chi = M (Ihh c ), h h h
i = 1, 2, . . . , m
(ii) Compute the Rayleigh quotient ih =
(chi )T K h (chi ) (chi )T Mh (chi )
,
i = 1, 2, . . . , m
(iii) Perform the RQI: For i = 1 : m do j = 0, x0i = chi /[(chi )T Mh (chi )]1/2 , i0 = ih While K h x ij −ij Mh x ij 2 > do Use MINRES to solve (K h −ij Mh +(Mh x ij )(Mh x ij )T )y ij+1 = Mh x ij for y ij+1 z ij+1 = y ij+1 /(1−(Mh x ij )T y ij+1 ) x ij+1 = z ij+1 /[(z ij+1 )T Mh (z ij+1 )]1/2 ij+1 = (x ij+1 )T K h (x ij+1 ) j = j +1 End While End For Note that Algorithm 4.2 can be easily modified to compute the extremum eigenvalues of the linear eigenvalue problem −u = u
in = (0, 1)2
(60)
with periodic boundary conditions (48). To study how many extremal eigenpairs on the coarse grid can be used as initial guesses for computing their counterparts on the fine grid, we quote the following two rules described in Reference [9] concerning the implementation of Algorithm 4.2. 1. Choose proper coarse and fine grids so that the multiplicity of eigenvalues on these two grids is the same. 2. Choose a proper number of eigenvalues to compute so that the multiplicity of eigenvalues on both grids is never missed. We remark here that there is a basic difference between two-grid discretization schemes and multilevel cycle iterations for solving elliptic eigenvalue problems. As we pointed out in Section 1, in the former the further correction on the coarse grid is replaced by the RQI because the second derivative of the operator equation with respect to the state variable is zero, see e.g. References [8, 9] for details. However, in the latter, we do not exploit the ideas of linear and quadratic approximation of the operator equations associated with elliptic eigenvalue problems. Therefore, it is necessary to perform coarse level updates of solutions combined with fine level iterations, which may increase the convergence rate by one order. We refer to References [1, 2, 33, 34] for details. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
73
At last but not the least, we wish to point out that for multiple eigenvalues, orthogonalization of the computed eigenvectors on the coarse grid is necessary, see e.g. References [33, 34]. For clustered eigenvalues as can be seen from our numerical examples in Section 5, without the orthogonalization process on the coarse grid, it might happen that the computed eigenvectors could mix together. A detailed investigation of the orthogonalization process in the two-grid discretization scheme combined with the Jacobi–Davidson method will be given elsewhere. 4.2. The SP system Suppose that we wish to compute the first k eigenpairs of the ESP, which is given in (11)–(14) with periodic boundary conditions on = (0, 1)2 . Since the ESP should be solved in an iterative way, we rewrite (11) as G(m , m , ) ≡ L(m , m )+ N (m ) = 0,
m = 1, 2, . . . , k, ∈ [0, 1]
(61)
where −m )m = 0 L(m , m ) = − 12 m +(W
(62)
is the linear SE problem, and N (m ) = W m
(63)
is the nonlinear term. Equation (61) is a parameter-dependent problem, which in general is solved by using numerical continuation methods. The ESP (11)–(14) is solved in Reference [9] using a two-grid centered difference continuation algorithm, where the nonlinear term 0 +1 |∇W |2 is set to be 1. In this section we will show how the algorithm described in Reference [9] can be generalized to solve the ESP, where the nonlinear Poisson equation is taken into account. For convenience we assume that the occurrence probability m of the initial states 0m (x) and the dopant density n ∗ are all constants, namely, m = c1 , m = 1, 2, . . . , k, and n ∗ = c2 . To begin with, we compute the first k eigenpairs of (61) with = 0 on the coarse grid. Next, we use the computed eigenvectors as the right-hand side for the nonlinear Poisson equation (12). That is, we solve k 2 2 −∇ ·(0 +1 |∇W | )∇W = c1 m −c2 (64) m=1
under the constraint (14) by an iterative way, where c1 and c2 are constants that satisfy the following equation: k 2 c1 (65) (n −n ∗ ) dx = m −c2 dx = 0
k
m=1
Equation (65) implies c1 m=1 2m dx = c2 dx. From the normalization condition (13), we obtain c1 k = c2 vol(), where vol() denotes the volume of the domain . Without loss of generality we choose c1 = 1, then c2 = k/vol(). Note that in the iterative process the nonlinear term |∇W |2 is obtained in the previous iteration that can be easily computed in the finite element code. Then we go back to compute the first k eigenpairs of (61) with = 0 , where the nonlinear potential W is the solution of (64) we just obtained. Afterward W is recomputed by solving (64) with Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
74
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
constraint (12). We repeat the process described above by increasing the parameter from = 0 to 2 0 and so on until j 0 = 1 is reached. Algorithm 4.3 A continuation algorithm for solving the quasilinear ESP (11)–(14) on the coarse grid. Input c1 := occurrence probability of each initial state 0m (x). c2 := dopant density. 0 := stepsize for the continuation algorithm on the nonlinear term. 0 , 1 := constants. For = 0 : 0 : 1 do (i) (ii) (iii) (iv)
Compute the first k eigenpairs of (61). Compute the right hand side of (64). Solve the nonlinear Poisson equation (64) iteratively with the constraint (14). If = 1, go to (i) and update the eigenpairs until the eigenvalues converge.
End For We will use the eigenpairs obtained in Algorithm 4.3 as starting approximate eigenpairs for computing wave functions of the SP system. Algorithm 4.4 A two-grid finite element algorithm for computing wave functions of the SP system (1)–(4). 1 1 ), . . . , (k , k ) ∈ V ×R 1. Use Algorithm 4.3 to find the first k approximate eigenpairs ( , h h h h h and the approximate nonlinear potential W of the quasilinear ESP on the coarse grid. h 2.
(i) Solve the linear problems on the fine grid: Find 1h , . . . , kh ∈ Vh such that 1 2
∇m h ·∇v +
m m (W h + W )h v = h
m v h
∀v ∈ Vh , m = 1, 2, . . . , k
(ii) Compute 1h , . . . , kh by the Rayleigh quotient:
m m 1 m 2 h + W )(h ) 2 ∇h ·∇ h + (W m = , h m 2 (h )
m = 1, 2, . . . , k
(iii) Compute Wh iteratively by solving
k m 2 c1 (0 +1 |∇Wh | )∇Wh ·∇v = (h ) −c2 v 2
m=1
∀v ∈ Vh with
Wh = 0
where W h is used in the first iterate on the nonlinear term of the equation above. 3. (i) Update the eigenpairs (1h , 1h ), . . . , (kh , kh ) by performing the RQI on the fine grid. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
Copyright q
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
0.00000000000 39.47970992989 39.47970992989 39.47970992989 39.47970992989 78.95941566262 78.95941566262 78.98971167237 78.98971167237 157.99425108728 157.99425108728 157.99425108728 157.99425108728 197.43661249913 197.43661249913 197.43661249913 197.43661249913 197.80106214674 197.80106214674 197.80106214674 197.80106214674
Coarse grid eigenvalue h 0.14[−13] 0.24[−12] 0.15[−12] 0.33[−12] 0.32[−12] 0.29[−11] 0.31[−11] 0.41[−12] 0.41[−12] 0.73[−12] 0.43[−12] 0.58[−12] 0.40[−12] 0.67[−13] 0.63[−13] 0.67[−13] 0.12[−12] 0.40[−12] 0.26[−12] 0.34[−12] 0.37[−12]
Residual 0.00000000000 39.47841808940 39.47841808940 39.47841808940 39.47841808940 78.95683594290 78.95683594290 78.95686187842 78.95686187842 157.91372922340 157.91372922340 157.91372922340 157.91372922340 197.39216784139 197.39216784139 197.39216784139 197.39216784139 197.39267588481 197.39267588481 197.39267588481 197.39267588481
Fine grid eigenvalue h 0.17[−12] 0.25[−3] 0.25[−3] 0.25[−3] 0.25[−3] 0.15[−3] 0.15[−3] 0.20[−2] 0.20[−2] 0.32[−2] 0.32[−2] 0.32[−2] 0.32[−2] 0.33[−2] 0.33[−2] 0.33[−2] 0.33[−2] 0.10[−1] 0.10[−1] 0.10[−1] 0.10[−1]
Residual — 39.47841792266 39.47841792266 39.47841792266 39.47841792266 78.95683584531 78.95683584531 78.95684348176 78.95684348176 157.91369078041 157.91369078043 157.91369078042 157.91369078042 197.39209915967 197.39209915967 197.39209915968 197.39209915968 197.39219455215 197.39219455216 197.39219455216 197.39219455216
RQI 1 — 0.41[−10] 0.41[−10] 0.41[−10] 0.41[−10] 0.44[−10] 0.45[−10] 0.38[−10] 0.38[−10] 0.32[−10] 0.45[−10] 0.32[−10] 0.32[−10] 0.42[−10] 0.42[−10] 0.40[−10] 0.40[−10] 0.51[−9] 0.51[−9] 0.51[−9] 0.51[−9]
Residual — — — — — — — — — — — — — — — — — 197.39219455217 197.39219455216 197.39219455216 197.39219455216
RQI 2 — — — — — — — — — — — — — — — — — 0.44[−10] 0.44[−10] 0.45[−10] 0.45[−10]
Residual
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2
Total RQIs
1 1 Table I. The first 21 eigenvalues of the discrete problem associated with (60) and (48), h = 32 , h = 256 .
2007 John Wiley & Sons, Ltd.
202 = 197.3920880217872
162 = 157.9136704174297
82 = 78.9568352087149
42 = 39.4784176043574
02 = 0
Exact eigenvalues
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
75
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
76
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
Table II. Implementing Algorithm 4.2 for the second eigenpair of the linear eigenvalue problem (60) with periodic boundary conditions (48). h
|0,1 −4h | |0,1 −h |
h = h2
h
|0,1 − h |
1 16 1 64 1 256 1 1024
39.503929651960
0.255120[−1]
39.480038938238
0.162133[−2]
39.479389824073 39.478913854376
|0,1 −4h | |0,1 −h |
h
|0,1 − h |
39.498562771820
0.201452[−1]
15.73522
39.478498918695
0.813143[−4]
247.74435
0.972220[−3]
1.66766
39.478417922663
0.318305[−6]
255.46021
0.496250[−3]
1.95913
39.478417605636
0.127893[−8]
248.88461
(a) 1 4 1 8 1 16 1 32
0,1 = 42 = 39.47841760435743 h
h = h2
u 0,1 −u h L 2
1 16 1 64 1 256 1 1024
0.4039662[−2]
u 0,1 −u 4h L 2
u 0,1 −u h L 2
u 0,1 − x h L 2
u 0,1 −x 4h L 2
u 0,1 −x h L 2
(b) 1 4 1 8 1 16 1 32
0.1396944[−3]
0.2075774[−2]
1.94610
0.5643071[−6]
247.55030
0.6760986[−3]
3.07022
0.2208141[−8]
255.55756
0.2220860[−3]
3.04431
0.3966620[−9]
5.56681
(ii) Update Wh iteratively by solving the following nonlinear equation with constraint: k m 2 c1 (0 +1 |∇Wh |2 )∇Wh ·∇v = (h ) −c2 v ∀v ∈ Vh with Wh = 0
m=1
(iii) Repeat 3(i) and 3(ii) until it converge. 4. Compute wave functions of the SP system: −ih t m m h (x), h (x, t) = e m
m = 1, 2, . . . , k
5. NUMERICAL RESULTS We report some numerical results concerning the implementations of Algorithms 4.2 and 4.4. In 1 1 Examples 1–3, we choose h = 32 on the coarse grid and h = 256 on the fine grid, where the domain was divided into two uniform triangulations T and T of quadratic Lagrange triangles. The h h dimensions of the corresponding finite dimensional subspaces V h and Vh of V are 1024 and 65 536, respectively. The accuracy tolerance for solving linear systems of equations in the MINRES iterative method is 0.5×10−10 . Stopping criteria in Algorithm 4.2 for Examples 1 and 2 are 0.5×10−10 and 0.5×10−8 , respectively. All of our computations were executed on a Pentium 4 computer using FORTRAN 95 with double precision arithmetic. The notation [±n] stands for multiplication by 10±n . Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
Copyright q
2007 John Wiley & Sons, Ltd.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
4.835701732025 44.357619875650 44.408221107723 44.410144158598 44.523835675750 83.945786462218 83.994302266952 84.064274267076 84.112790127502 162.884358737914 162.884359639090 162.951463469771 162.951468031607 202.459382770608 202.459383397733 202.469314414232 202.469314677017 202.827215552148 202.827216173706 202.850699598214 202.850699866593
Coarse grid eigenvalue h
0.56[−10] 0.53[−10] 0.11[−9] 0.30[−10] 0.42[−10] 0.37[−10] 0.37[−10] 0.35[−10] 0.47[−10] 0.44[−10] 0.36[−10] 0.34[−10] 0.45[−10] 0.42[−10] 0.38[−10] 0.32[−10] 0.47[−10] 0.40[−10] 0.35[−10] 0.42[−10] 0.28[−10]
Residual 4.835696282636 44.356275498174 44.406878428380 44.408818626900 44.522513943523 83.930773563951 83.983122143314 84.039999246285 84.092347876832 162.803418924235 162.803419827092 162.870731883247 162.870736453561 202.413165377865 202.413166622381 202.416539167221 202.416539672486 202.420638655748 202.420639894465 202.450822383808 202.450822897169
Fine grid eigenvalue h 0.20[−4] 0.35[−3] 0.35[−3] 0.33[−3] 0.33[−3] 0.14[−2] 0.12[−2] 0.18[−2] 0.16[−2] 0.36[−2] 0.36[−2] 0.35[−2] 0.35[−2] 0.35[−2] 0.35[−2] 0.39[−2] 0.39[−2] 0.10[−1] 0.10[−1] 0.10[−1] 0.10[−1]
Residual 4.835696281322 44.356275002153 44.406877940872 44.408818271399 44.522513578153 83.929400900088 83.980012584041 84.043087378481 84.093698937772 162.803368007865 162.803368910724 162.870684153830 162.870688724145 202.406702166668 202.406705557974 202.392170122472 202.392171109532 202.427515419411 202.427518742729 202.475192640022 202.475193596076
RQI 1 0.48[−10] 0.41[−10] 0.47[−10] 0.48[−10] 0.35[−10] 0.57[−6] 0.34[−5] 0.33[−5] 0.56[−6] 0.88[−10] 0.87[−10] 0.67[−10] 0.65[−10] 0.11[−3] 0.10[−3] 0.18[−3] 0.18[−3] 0.10[−3] 0.10[−3] 0.17[−3] 0.17[−3]
Residual — — — — — 83.929400802473 83.980003736173 84.043096098612 84.093699032324 — — — — 202.395210284989 202.395215772734 202.376995428612 202.376993732678 202.438916649295 202.438921788059 202.489818820045 202.489819720415
RQI 2 — — — — — 0.46[−10] 0.47[−9] 0.46[−9] 0.37[−10] — — — — 0.61[−4] 0.61[−4] 0.33[−4] 0.33[−4] 0.54[−4] 0.54[−4] 0.30[−4] 0.30[−4]
Residual — — — — — — — — — — — — — 202.391330613513 202.391335218160 202.376528066906 202.376528966700 202.441891424766 202.441896007628 202.490223282510 202.490224185363
RQI 3
— — — — — — — — — — — — — 0.55[−5] 0.55[−5] 0.14[−6] 0.14[−6] 0.36[−5] 0.36[−5] 0.11[−6] 0.11[−6]
Residual
— — — — — — — — — — — — — 202.391300939694 202.391305509998 202.376528050548 202.376528953401 202.441903919492 202.441908489799 202.490223287941 202.490224190792
RQI 4
— — — — — — — — — — — — — 0.32[−8] 0.32[−8] 0.50[−10] 0.48[−10] 0.89[−9] 0.89[−9] 0.50[−10] 0.50[−10]
Residual
1 1 1 1 1 2 2 2 2 1 1 1 1 4 4 4 4 4 4 4 4
Total RQIs
Table III. The first 21 eigenvalues and residuals of the corresponding eigenvectors of the discretized Schr¨odinger eigenvalue problem 1 1 h = 32 , h = 256 , implementing the MINRES with 20 ( f (x1 , x2 ) = 5+3 sin(2x1 )+2 cos(2x2 )) in 2D with periodic boundary conditions, iterations in Step 2(i) of Algorithm 4.2.
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
77
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
2
2
1.1
1
1
1 2
1 0.9
0.5 xis x -a
0.5 x -a 2 xis
(b)
1
1
u(x1,x2)
2
1 0
0.5 xis x -a
0 -1 -2 1
0.5 x -a 2 xis
(d)
1 0
0
0.5 xis x -a
0.5 x -a 2 xis
(e)
1
1 2
u(x ,x )
3 2 1 0 -1 -2 -3 1 0.5 x -a 2 xis
1 0 0
0
0
xis x 1-a
3 2 1 0 -1 -2 -3 1 0.5 x -a 2 xis
0.5 xis x 1-a
1
(h)
0 0
1
0 0
0.5 x -a 2 xis
0 0
(f )
1 0.5 xis x -a
0.5 xis x 1-a
1 0.5 xis x -a 1
3 2 1 0 -1 -2 -3 1
1 x -a0.5 2 xis
(i)
1
0.5 x -a 2 xis
3 2 1 0 -1 -2 -3 1
0.5
u(x1,x2)
-2 1
(c)
1
2
-1
0 0
0 -1 -2 1
1
u(x1,x2)
0 0
(a)
u(x1,x2)
-1
1 0.5 x -a 2 xis
u(x1,x2)
0 -2 1
0.8 1
(g)
u(x1,x2)
1.2
u(x ,x )
u(x1,x2)
78
0 0
0.5 xis x 1-a
Figure 3. The first nine eigenfunctions of the Schr¨odinger eigenvalue problem (47) with periodic boundary conditions (48), where the linear potential f (x1 , x2 ) = 5+3 sin(2x1 )+2 cos(2x2 ): (a) 1 = 4.835696281322; (b) 2 = 44.356275002153; (c) 3 = 44.406877940872; (d) 4 = 44.408818271399; (e) 5 = 44.522513578153; (f) 6 = 83.929400802473; (g) 7 = 83.980003736173; (h) 8 = 84.043096098612; and (i) 9 = 84.093699032324.
Example 1 The first test problem is the linear eigenvalue problem (60) with periodic boundary conditions (48). The exact eigenvalues of (60) with (48) are m,n = (2m)2 +(2n)2 where m, n are integers. We wish to find the first 21 eigenpairs of the discrete problem. Table I lists the numerical results, where we used the MINRES to solve each SPD linear system with 20 iterations in Step 2(i) of Algorithm 4.2. In order to study the convergence rate of Algorithm 4.2, 1 1 we compute the second eigenpair of (60) with (48) using h = h 2 with h = 14 , 18 , 16 , and 32 . Let h h (u 0,1 , 0,1 ) denote the second exact eigenpair of (60) with (48), and (u h , h ) and (x , ) denote the corresponding eigenpair on the fine grid and the RQI solution in Algorithm 4.2. From the Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
Copyright q
2007 John Wiley & Sons, Ltd.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
4.836229977645 44.358013172448 44.408449803967 44.410370060726 44.523692294477 83.945873093816 83.994218699693 84.064006320436 84.112351987613 162.884711873319 162.884712767729 162.951601152006 162.951605679592 202.459315129779 202.459315750742 202.469236378615 202.469236638092 202.827125740886 202.827126355556 202.850513285949 202.850513551741
h
Coarse grid
0.12[−9] 0.12[−9] 0.13[−9] 0.11[−9] 0.13[−9] 0.12[−9] 0.12[−9] 0.12[−9] 0.14[−9] 0.12[−9] 0.13[−9] 0.12[−9] 0.13[−9] 0.12[−9] 0.11[−9] 0.11[−9] 0.11[−9] 0.12[−9] 0.12[−9] 0.12[−9] 0.13[−9]
Residual 4.836224545899 44.356668963592 44.407107288648 44.409044637633 44.522370657518 83.930869006993 83.983055975638 84.039713991958 84.091901018043 162.803773416990 162.803774313067 162.870870259607 162.870874795614 202.413108956794 202.413110189449 202.416511405152 202.416511903825 202.420537635642 202.420538860773 202.450585285435 202.450585793920
h in Step 2
0.19[−4] 0.35[−3] 0.35[−3] 0.33[−3] 0.33[−3] 0.14[−2] 0.12[−2] 0.18[−2] 0.16[−2] 0.36[−2] 0.36[−2] 0.35[−2] 0.35[−2] 0.35[−2] 0.35[−2] 0.39[−2] 0.39[−2] 0.10[−1] 0.10[−1] 0.10[−1] 0.10[−1]
Residual 4.836224778182 44.356668753808 44.407106796707 44.409044646935 44.522369959827 83.929492448116 83.979930497797 84.042817762015 84.093255817194 162.803722679059 162.803723575106 162.870822598807 162.870827134623 202.391304656417 202.391309192133 202.376580617464 202.376581513566 202.441742752436 202.441747288199 202.489905873022 202.489906769077
h in Step 3
Fine grid
0.49[−10] 0.47[−10] 0.49[−10] 0.34[−10] 0.50[−10] 0.49[−10] 0.49[−9] 0.47[−9] 0.49[−10] 0.80[−10] 0.84[−10] 0.67[−10] 0.64[−10] 0.40[−10] 0.42[−10] 0.51[−10] 0.50[−10] 0.38[−10] 0.45[−10] 0.50[−10] 0.50[−10]
Residual 1 1 1 1 1 2 2 2 2 1 1 1 1 5 5 4 4 5 5 4 4
RQIs 4.836227894180 44.356670961331 44.407108253891 44.409045712038 44.522369387239 83.929492604995 83.979929904671 84.042816281646 84.093253587692 162.803724767761 162.803725663788 162.870823417125 162.870827952874 202.391304566647 202.391309102290 202.376580655603 202.376581551691 202.441741912940 202.441746448637 202.489904274179 202.489905170220
h in Step 3
0.50[−10] 0.49[−10] 0.41[−10] 0.49[−10] 0.30[−10] 0.49[−10] 0.45[−10] 0.31[−10] 0.50[−10] 0.48[−10] 0.48[−10] 0.49[−10] 0.48[−10] 0.50[−10] 0.45[−10] 0.48[−10] 0.50[−10] 0.37[−10] 0.49[−10] 0.43[−10] 0.50[−10]
Residual 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
RQIs
4.836227889147 44.356670957600 44.407108251644 44.409045709966 44.522369388492 83.929492604250 83.979929905442 84.042816284244 84.093253591821 162.803724764366 162.803725660393 162.870823415792 162.870827951547 202.391304566645 202.391309102290 202.376580655200 202.376581551287 202.441741914458 202.441746450151 202.489904277123 202.489905173161
h in Step 3
Fine grid
0.18[−9] 0.17[−9] 0.20[−9] 0.15[−9] 0.21[−9] 0.14[−9] 0.17[−9] 0.20[−9] 0.23[−9] 0.18[−9] 0.18[−9] 0.18[−9] 0.18[−9] 0.17[−9] 0.17[−9] 0.16[−9] 0.16[−9] 0.20[−9] 0.20[−9] 0.21[−9] 0.21[−9]
Residual
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
RQIs
2 2 2 2 2 3 3 3 3 2 2 2 2 6 6 5 5 6 6 5 5
Total RQIs
Table IV. The first 21 eigenvalues of the discretized quasilinear ESP with periodic boundary conditions, computed by Algorithm 4.4 with 1 1 (x1 , x2 ) = 5+3 sin(2x1 )+2 cos(2x2 ) and 0 = 1, 1 = 0.3. h = 32 , h = 256 . The linear potential W
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
79
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
80
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
-0.7
0.65 Im(ψ )
1
1
Re(ψ )
0.6 0.55 0.5 0.45 1
-0.8 -0.9 1 1
1 0.5 x 2 axi s
0.5 x 2 axi s
0.5 0
0
xis x 1-a
Im(ψ ) 2
2
Re(ψ )
0.4 0.2
0 -1 1 0.5
x 2 axi s
1 0.5
0.5 0
0
0 -0.2 -0.4 1
1
x 2 axi s
s
xi x 1-a
0.04
2
0.02
1 6
Im(ψ )
6
0
1
1.5 1
Re(ψ )
0
0.5 xis x -a
0 -0.02
0.5 0
0
axis
x 1-
0 -1 -2 1
-0.04 1
1
1 0.5
x 2 axi s
0.5
0.5 0
0
x 2 axi s
s
xi x 1-a
0.5 0
0
s
xi x 1-a
Figure 4. The contours of the real and imaginary parts of the wave functions 1 , 2 , 6 of the SP system (x1 , x2 ) = 5+3 sin(2x1 )+2 cos(2x2 ), 0 = 1, and 1 = 0.3, at time t = 160. with W
numerical results shown in Table II, we have that |0,1 −h | ≈ O(h 4 ),
u 0,1 − x h L 2 ≈ O(h 4 )
Example 2 Consider the Schr¨odinger eigenvalue problem (47)–(48) with linear potential f (x 1 , x2 ) = 5+ 3 sin(2x1 )+2 cos(2x2 ). We implemented Algorithm 4.2 to find the first 21 eigenpairs of the discrete problem. Table III shows that the first 21 eigenvalues consist of one simple eigenvalue and four clusters of eigenvalues, where the first three clusters consist of four close eigenvalues, and the last cluster consists of eight close eigenvalues. The cluster structure is preserved on the fine grid. Figure 3 shows the first nine eigenfunctions of this problem. For the last eight eigenpairs we need to perform four RQIs. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
¨ COMPUTATION OF WAVE FUNCTIONS OF THE SCHRODINGER–POISSON SYSTEM
81
Example 3 Computing eigenpairs of the ESP and wave functions of the SP system. Consider the SP system (x1 , x2 ) = 5+3 sin(2x1 )+2 cos(2x2 ) and 0 = 1, 1 = 0.3. In order (1)–(4) with linear potential W to compare with the result of Example 2, we omitted the coefficient 12 in the Laplacian. We implemented Algorithm 4.4 to find the first 21 eigenpairs of the ESP and the corresponding wave functions of the SP system. Table IV lists the first 21 eigenvalues of the ESP and the residuals of the associated eigenvectors, which shows that the eigenvalues agree with those of the SE problem at least to two decimal digits. The contours of the real and imaginary parts of the wave functions 1 , 2 , and 6 at time t = 160 are displayed in Figure 4. 6. CONCLUSIONS We have presented a time-independent numerical scheme for computing wave functions of the SP system. By using the well-known separation of variables, the SP system is transformed into the ESP. A two-grid finite element discretization scheme is described to compute the first few eigenpairs of the ESP. The first few wave functions of the SP system can be easily obtained using (10). The proposed numerical scheme has the following advantages: 1. It is not necessary to discretize the left-hand side of (1), namely, the partial derivative of the wave function with respect to the time variable t. 2. The wave functions of the SP system at any time scale can be easily evaluated whenever the eigenpairs of the ESP are obtained. 3. The major computational difficulties such as closely clustered eigenvalues that occur in the SP system can be effectively computed using the proposed algorithm. 4. The rate of convergence of the proposed two-grid finite element discretization scheme is O(h 4 ), which is a significant improvement to the two-grid centered difference discretization scheme we proposed earlier. ACKNOWLEDGEMENTS
The authors would like to thank the two referees for their valuable comments that have improved the original version of this paper. Supported by the National Science Council of R.O.C. (Taiwan) through Project NSC 95-2115-M-005-004-MY3. REFERENCES 1. Brandt A, Bernholc J, Binder K (eds). Multiscale Computational Methods in Chemistry and Physics. NATO Science Series. IOS Press: Amsterdam, 2001. 2. Brandt A. Multiscale scientific computation: review 2000. Survery Report, Weizmann Institute of Science, Rehovot, Israel. 3. Illner R, Kavian O, Lange H. Stationary solutions of quasi-linear Schr¨odinger–Poisson systems. Journal of Differential Equations 1998; 145:1–16. 4. Ringhofer C, Soler J. Discrete Schr¨odinger–Poisson systems preserving energy and mass. Applied Mathematics Letters 2000; 13:27–32. 5. Chang S-L, Chien C-S, Jeng B-W. Computing wave functions of nonlinear Schr¨odinger equations: a timeindependent approach. Journal of Computational Physics 2007; 226:104–130. 6. Xu J. A novel two-grid method for semilinear elliptic equations. SIAM Journal on Scientific Computing 1994; 15:231–237. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
82
C.-S. CHIEN, B.-W. JENG AND Z.-C. LI
7. Chien C-S, Jeng B-W. A two-grid discretization scheme for semilinear elliptic eigenvalue problems. SIAM Journal on Scientific Computing 2006; 27:1287–1304. 8. Xu J, Zhou A. A two-grid discretization scheme for eigenvalue problems. Mathematics of Computation 1999; 70:17–25. 9. Chang S-L, Chien C-S, Jeng B-W. An efficient algorithm for the Schr¨odinger–Poisson eigenvalue problem. Journal of Computational and Applied Mathematics 2007; 205:509–532. 10. Costiner S, Ta’asan S. Simultaneous multigrid techniques for nonlinear eigenvalue problems: solutions of the nonlinear Schr¨odinger–Poisson eigenvalue problem in two and three dimensions. Physical Review E 1995; 52:1181–1192. 11. Schepper HD. Finite element methods for eigenvalue problems on a rectangle with (semi-)periodic boundary conditions on a pair of adjacent sides. Computing 2000; 64:191–206. 12. Schepper HD. A finite element method for differential eigenvalue problems with mixed classical and (semi-)periodic boundary conditions. Applied Mathematics and Computation 2001; 121:1–15. 13. Hall CA, Porsching TA. Numerical Analysis of Partial Differential Equations. Prentice-Hall: Englewood Cliffs, NJ, 1990. 14. Brenner SC, Scott LR. The Mathematical Theory of Finite Element Methods. Springer: New York, 1994. 15. Babuˇska I, Osborn J. Eigenvalue problems. In Finite Element Methods (Part 1), Ciarlet PG, Lions JL (eds), Handbook of Numerical Analysis, vol. II. North-Holland: Amsterdam, 1991; 641–787. ´ 16. Raviart PA, Thomas JM. Introduction a` l’Analyse Num´erique des Equations aux D´eriv´ees Partielles. Masson: Paris, 1983. 17. Ciarlet PG. The Finite Element Method for Elliptic Problems. North-Holland: Amsterdam, 1978. 18. Li ZC. Combined Methods for Elliptic Equations with Singularities, Interfaces and Infinities. Kluwer Academic Publishers: Dordrecht, 1998. 19. Babuˇska I. The finite element method with penalty. Mathematics of Computation 1973; 27:221–228. 20. Barrett JW, Elliott CM. Finite element approximation of the Dirichlet problem using the boundary penalty method. Numerische Mathematik 1986; 49:343–366. 21. Dussault JP. Numerical stability and efficiency of penalty algorithms. SIAM Journal on Numerical Analysis 1995; 32:296–317. 22. King JT. New error bounds for the penalty method and extrapolation. Numerische Mathematik 1974; 23:153–165. 23. King JT, Serbin SM. Computational experiments and techniques for the penalty method with extrapolation. Mathematics of Computation 1978; 32:111–126. 24. Shi ZC. On the convergence rate of the boundary penalty method. International Journal for Numerical Methods in Engineering 1984; 20:2027–2032. 25. Utku M, Carey GF. Boundary penalty techniques. Computer Methods in Applied Mechanics and Engineering 1982; 30:103–118. 26. Davidson ER. The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real symmetric matrices. Journal of Computational Physics 1975; 17:87–94. 27. Saad Y. Numerical Methods for Large Eigenvalue Problems. Manchester University Press: Manchester, U.K., 1992. 28. Sleijpen GLG, van der Vorst HA. A Jacobi–Davidson iteration method for linear eigenvalue problems. SIAM Journal on Matrix Analysis and Applications 1996; 17(2):401–425. 29. Sleijpen GLG, Booten AGL, Fokkema DR, van der Vorest HA. Jacobi–Davidson type methods for generalized eigenproblems and polynomial eigenproblems. BIT 1996; 36(3):595–633. 30. Lui SH, Golub GH. Homotopy method for the numerical solution of the eigenvalue problem of self-adjoint partial differential operators. Numerical Algorithms 1995; 10:363–378. 31. Smith CF, Peter AF, Mittra R. A conjugate gradient algorithm for the treatment of multiple incident electromagnetic fields. IEEE Transactions on Antennas and Propagation 1989; 37:1490–1493. 32. Dul FA. MINRES and MINERR are better than SYMMLQ in eigenpair computations. SIAM Journal on Scientific Computing 1998; 19:1767–1782. 33. Beck TL. Multiscale methods for self-consistent electronic structure in real space. In Multiscale Computational Methods in Chemistry and Physics, Brandt A, Bernholc K, Binder K (eds), NATO Science Series. IOS Press: Amsterdam, 2001; 90–103. 34. Bernholc J, Briggs EL, Buongiorno Nardelli M, Fattebert JL, Ramamoorthy M, Schmidt WG, Sullivan DJ. Largescale multilevel solutions of Kohn–Sham equations: methodology and applications. In Multiscale Computational Methods in Chemistry and Physics, Brandt A, Bernholc J, Binder K (eds), NATO Science Series. IOS Press: Amsterdam, 2001; 65–89. Copyright q
2007 John Wiley & Sons, Ltd.
Numer. Linear Algebra Appl. 2008; 15:55–82 DOI: 10.1002/nla
NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS Numer. Linear Algebra Appl. 2008; 15:83 Published online in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/nla.573
Call for Papers: Special Issue on ‘Recent Advances in Computational Techniques for Biomedical Imaging’ Communications in Numerical Methods in Engineering (CNM) Communications in Numerical Methods in Engineering will publish a special issue on ‘Recent Advances in Computational Techniques for Biomedical Imaging’. The Guest Editors for this issue will be Professor Guo-Wei Wei, Department of Mathematics and Department of Electrical and Computer Engineering, Michigan State University and Professor Ge Wang, Director of Biomedical Imaging Division, Virginia Polytechnic Institute and State University. Recent advances in biomedical imaging have revolutionized diagnosis, therapy and discovery in both clinical and pre-clinical settings. Although traditional tomographic and post-processing methods become increasingly sophisticated, emerging new modalities play more and more critical roles in anatomical, functional, cellular and molecular imaging. Mathematical and computational techniques have been instrumental to these developments and their momentum. We invite the original papers and high-quality overviews on all the relevant topics including but not limited to: • • • • • •
Algorithms for biomedical image reconstruction Techniques for biomedical image analysis and visualization Forward models and inverse solutions Interface problems in biomedical imaging Multi-modal imaging Evaluation and comparison of biomedical imaging modalities
Paper Submission Details Completed papers should conform to the journal’s style and to the instructions for authors, which can be found on the journal’s homepage under ‘For Authors’. Papers have to be submitted online via the journal’s homepage to http://www3.interscience.wiley.com/cgibin/jabout/5902/ForAuthors.html under ‘Online Submission’. Authors must select Guo-Wei Wei or Ge Wang as Editor. Each submission must be clearly identified as a submission for this special issue, and the special issue code, RACTI, must be entered in the Special Issue Title field, when requested. Publication will take place according to the following schedule: Manuscript due: 1 April 2008 First review completion: Mid 2008 Anticipated publication date: End of 2008 Guest Editors Prof. Guo-Wei Wei Submitting Editor Department of Mathematics and Department of Electrical and Computer Engineering Michigan State University, MI, U.S.A. E-mail: [email protected] Prof. Ge Wang Director of Biomedical Imaging Division Virginia polytechnic Institute and State University, VA, U.S.A. E-mail: [email protected], [email protected]
Copyright q
2008 John Wiley & Sons, Ltd.
