[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the robustness and optimality of algebraic multilevel methods for reaction–diffusion type problems

  • Published:
Computing and Visualization in Science

Abstract

This paper is on preconditioners for reaction–diffusion problems that are both, uniform with respect to the reaction–diffusion coefficients, and optimal in terms of computational complexity. The considered preconditioners belong to the class of so-called algebraic multilevel iteration (AMLI) methods, which are based on a multilevel block factorization and polynomial stabilization. The main focus of this work is on the construction and on the analysis of a hierarchical splitting of the conforming finite element space of piecewise linear functions that allows to meet the optimality conditions for the related AMLI preconditioner in case of second-order elliptic problems with non-vanishing zero-order term. The finite element method (FEM) then leads to a system of linear equations with a system matrix that is a weighted sum of stiffness and mass matrices. Bounds for the constant \(\gamma \) in the strengthened Cauchy–Bunyakowski–Schwarz inequality are computed for both mass and stiffness matrices in case of a general \(m\)-refinement. Moreover, an additive preconditioner is presented for the pivot blocks that arise in the course of the multilevel block factorization. Its optimality is proven for the case \(m=3\). Together with the estimates for \(\gamma \) this shows that the construction of a uniformly convergent AMLI method with optimal complexity is possible (for \(m \ge 3\)). Finally, we discuss the practical application of this preconditioning technique in the context of time-periodic parabolic optimal control problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Axelsson, O.: Iterative Solution Methods. Cambridge University Press, Cambridge (1994)

    Book  MATH  Google Scholar 

  2. Axelsson, O., Barker, V.: Finite Element Solution of Boundary Value Problems: Theory and Computations. Academic Press, Orlando (1984)

    Google Scholar 

  3. Axelsson, O., Blaheta, R.: Two simple derivations of universal bounds for the C.B.S. inequality constant. Appl. Math. 49(1), 57–72 (2004)

  4. Axelsson, O., Padiy, A.: On the additive version of the algebraic multilevel iteration method for anisotropic elliptic problems. SIAM J. Sci. Comput. 20(5), 1807–1830 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  5. Axelsson, O., Vassilevski, P.: Algebraic multilevel preconditioning methods. I. Numer. Math. 56(2–3), 157–177 (1989)

  6. Axelsson, O., Vassilevski, P.: Algebraic multilevel preconditioning methods. II. SIAM J. Numer. Anal. 27(6), 1569–1590 (1990)

  7. Axelsson, O., Vassilevski, P.: Variable-step multilevel preconditioning methods, I: self-adjoint and positive definite elliptic problems. Numer. Linear Algebra Appl. 1(1), 75–101 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  8. Axelsson, O., Vassilevski, P.: The AMLI Method: An Algebraic Multilevel Iteration Method for Positive Definite Sparse Matrices. University of Nijmegen, Departement of Mathematics (1999)

  9. Ciarlet, P.: The Finite Element Method for Elliptic Problems. North-Holland, Amsterdam, 1978. Republished by SIAM in April 2002

  10. Collins, G.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975). Lecture Notes in Comput. Sci., vol. 33, pp. 134–183 (1975)

  11. Collins, G., Hong, H.: Partial cylindrical algebraic decomposition for quantifier elimination. J. Symb. Comput. 12(3), 299–328 (1991)

  12. Kauers, M.: How to use cylindrical algebraic decomposition. Semin. Lothar. Comb. 65(B65a), 1–16 (2011)

    MathSciNet  Google Scholar 

  13. Kollmann, M., Kolmbauer, M.: A preconditioned MinRes solver for time-periodic parabolic optimal control problems. Numer. Linear Algebra Appl. 20(5), 761–784 (2013)

  14. Kollmann, M., Kolmbauer, M., Langer, U., Wolfmayr, M., Zulehner, W.: A finite element solver for a multiharmonic parabolic optimal control problem. Comput. Math. Appl. 65(3), 469–486 (2013)

    Article  MathSciNet  Google Scholar 

  15. Kraus, J.: An algebraic preconditioning method for M-matrices: linear versus non-linear multilevel iteration. Numer. Linear Algebra Appl. 9(8), 599–618 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  16. Kraus, J.: Additive Schur complement approximation and application to multilevel preconditioning. SIAM J. Sci. Comput. 34(6), A2872–A2895 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  17. Kraus, J., Lymbery, M., Margenov, S.: Robust multilevel methods for quadratic finite element anisotropic elliptic problems. Numer. Linear Algebra Appl. 21(3), 375–398 (2014)

  18. Kraus, J., Margenov, S.: Robust Algebraic Multilevel Methods and Algorithms, Volume 5 of Radon Series on Computational and Applied Mathematics. De Gruyter, Berlin (2009)

    Book  Google Scholar 

  19. Langer, U., Wolfmayr, M.: Multiharmonic finite element solvers for time-periodic parabolic optimal control problems. Proc. Appl. Math. Mech. (PAMM) 12(1), 687–688 (2012)

    Article  Google Scholar 

  20. Langer, U., Wolfmayr, M.: Multiharmonic finite element analysis of a time-periodic parabolic optimal control problem. J. Numer. Math. 21(4), 265–300 (2013)

  21. Lazarov, R., Margenov, S.: CBS constants for graph-Laplacians and application to multilevel methods for discontinuous Galerkin systems. J. Complex. 4–6, 498–515 (2007)

    Article  MathSciNet  Google Scholar 

  22. Lymbery, M., Margenov, S.: Robust semi-coarsening multilevel preconditioning of biquadratic fem systems. Cent. Eur. J. Math. 10(1), 357–369 (2012)

  23. Maitre, J., Musy, F.: The contraction number of a class of two-level methods: an exact evaluation for some finite element subspaces and model problems. Lect. Notes Math. 960, 535–544 (1982)

  24. Mense, C., Nabben, R.: On algebraic multilevel methods for non-symmetric systems—convergence results. Electron. Trans. Numer. Anal. 30, 323–345 (2008)

    MathSciNet  MATH  Google Scholar 

  25. Notay, Y., Vassilevski, P.: Recursive Krylov-based multigrid cycles. Numer. Linear Algebra Appl. 15(5), 473–487 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  26. Paige, C., Saunders, M.: Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12(4), 617–629 (1975)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We want to thank Ulrich Langer for encouraging us to look deeper into this very interesting topic. Moreover, we want to thank Veronika Pillwein for introducing us to the symbolic computational algorithm Cylindrical Algebraic Decomposition (CAD). The research has been supported by the Doctoral Program “Computational Mathematics: Numerical Analysis and Symbolic Computation”. The authors gratefully acknowledge the financial support by the Austrian Science Fund (FWF) under the grant W1214, project DK4, the Johannes Kepler University of Linz and the Federal State of Upper Austria.

Author information

Authors and Affiliations

  1. Johann Radon Institute for Computational and Applied Mathematics, Linz, Austria

    Johannes Kraus

  2. Doctoral Program Computational Mathematics, Johannes Kepler University Linz, Linz, Austria

    Monika Wolfmayr

Authors
  1. Johannes Kraus
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Monika Wolfmayr
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Monika Wolfmayr.

Additional information

Communicated by Gabriel Wittum.

The research was supported by the Austrian Scienc Fund (FWF) under the grant W1214-N15, project DK4, as well as by the strategic program “Innovatives OÖ 2010 plus” by the Upper Austrian Government.

Appendices

Appendix 1: Proof of Lemma 1

The element mass matrix for a given arbitrary non-degenerate triangle \(e\) is given by

$$\begin{aligned} M_e(u,v) = \int _e u v \, de. \end{aligned}$$

We introduce the notations \(h = |OA|, p = |OB|\) and \(q = |OC|\), where \(O\) is the origin, see Fig. 1. Then we have the following relations given:

$$\begin{aligned} b = \frac{p}{h}, \quad c = \frac{q}{h}, \quad a = \cot (\pi - (\theta _2 + \theta _3)) = \frac{h^2 - p q}{h(p+q)}. \end{aligned}$$

The element basis functions are given by

$$\begin{aligned} \phi _1 = - \frac{x}{h}, \quad \phi _2 = \frac{q x + h(q-y)}{h(p+q)}, \quad \phi _3 = \frac{p x + h(p+y)}{h(p+q)}. \end{aligned}$$

Moreover,

$$\begin{aligned} |e| = \int \, de = \frac{h(p+q)}{2} = J_e \cdot \frac{1}{2}, \end{aligned}$$

where \(J_e = h^2 (b+c)\) is the Jacobi determinant. We obtain the following first two entries of the element mass matrix:

$$\begin{aligned} {M_e}_{11} = \int _{-h}^0 \int _{-p/h x - p}^{q/h x + q} (\phi _1)^2 \,dy \, dx = \frac{h^2(b+c)}{12} \end{aligned}$$

and

$$\begin{aligned} {M_e}_{12} = \int _{-h}^0 \int _{-p/h x - p}^{q/h x + q} \phi _1 \phi _2 \,dy \, dx = \frac{h^2(b+c)}{24}. \end{aligned}$$

Analogously, we obtain all other entries and we finally derive the element mass matrix (19). \(\square \)

Appendix 2: Proof of Theorem 1

Let \(m_c = h^2 (b+c) /24\). The global CBS constant can be estimated by the the maximum of the local CBS constants on the macro elements (7), which can be again computed via the rule (8), i.e., \(\gamma _{M,E}^2 = 1 - \lambda ^{\min }_E\), where \(\lambda ^{\min }_E\) is the minimal eigenvalue of the eigenvalue problem (22), which we write in the form

$$\begin{aligned} \mathbf{v}_{E:2}^T \left( S_M - \lambda \, \tilde{M}_{E:22} \right) \mathbf{v}_{E:2} = 0, \end{aligned}$$

We try to find a lower bound \(\underline{\lambda ^{\min }_E}\) for the minimal eigenvalue \(\lambda ^{\min }_E\) such that

$$\begin{aligned} \mathbf{v}_{E:2}^T \left( S_M - \underline{\lambda ^{\min }_E} \, \tilde{M}_{E:22} \right) \mathbf{v}_{E:2} \ge 0. \end{aligned}$$

For that reason, we estimate the Schur complement \(S_M\) from below by \(\underline{S_M}\), and, after that we solve the problem \(\mathbf{v}_{E:2}^T (\underline{S_M} - \lambda \, \tilde{M}_{E:22} ) \mathbf{v}_{E:2} = 0\). For every \(m\)-refinement, we systematically use a bottom-up lexicographical ordering for the fine nodes and number the three coarse nodes last. Hence, the lower right block \(M_{E:22}\) of the macro element mass matrix is always \(M_{E:22} = 2 \, m_c \, I\), where \(I\) is the identity matrix. Let \(N_E\) denote the number of nodes on a macro element subdivided into \(m^2\) elements. The Schur complement \(S_M\) can be estimated from below in the following way:

$$\begin{aligned} S_M&= M_{E:22} - M_{E:21} \, M_{E:11}^{-1} \, M_{E:12} \\&= 2 \, m_c \, I - M_{E:21} \, M_{E:11}^{-1} \, M_{E:12} \\&\ge 2 \, m_c \, I - \frac{1}{6} \, m_c^{-1} \, M_{E:21} \, I \, M_{E:12}, \end{aligned}$$

where we use the estimate

$$\begin{aligned} M_{E:11} \ge \min _{i \in \{1,\ldots ,N_E\}}{(M_{E:11})_{ii}} \, I = 6 \, m_c \, I \end{aligned}$$

because the weakly diagonally dominant matrix \(M_{E:11}\) has only the diagonal entries \(12 \, m_c\) and \(6 \, m_c\). Moreover, since the matrices \(M_{E:12}\) and \(M_{E:21} = (M_{E:12})^T\) have exactly two entries equal to one in each of the three columns and rows, respectively, we obtain

$$\begin{aligned} M_{E:21} \, M_{E:12} = (M_{E:12})^T \, M_{E:12} = 2 \, m_c^2 \, I \end{aligned}$$

and finally the Schur complement \(S_M\) can be estimated from below by

$$\begin{aligned} S_M&\ge 2 \, m_c \, I - \frac{1}{6} \, m_c^{-1} \, 2 \, m_c^2 \, I = 2 \, m_c \, I - \frac{1}{3} \, m_c \, I, \\&= \frac{5}{3} \, m_c \, I. \end{aligned}$$

Next we have that

$$\begin{aligned} \tilde{M}_{E:22}&= \,M_{E:22} + J_{E:12}^T \, M_{E:12} + M_{E:21} \, J_{E:12} \\&\quad +\,J_{E:12}^T \, M_{E:12} \, J_{E:12} \\&= \,m^2 \, M_e \end{aligned}$$

with a transformation matrix \(J_{E:12}\) of the from (14). Then

$$\begin{aligned} J_{E:12}^T \, M_{E:12} = m_c \left( \begin{array}{c@{\quad }c@{\quad }c} \frac{2 \, m-2}{m} &{} \frac{1}{m} &{} \frac{1}{m} \\ \frac{1}{m} &{} \frac{2 \, m-2}{m} &{} \frac{1}{m} \\ \frac{1}{m} &{} \frac{1}{m} &{} \frac{2 \, m-2}{m} \\ \end{array} \right) \end{aligned}$$

because \(M_{E:12}\) has exactly two entries with value one in each row and \(J_{E:12}\) has the value \((m-1)/m\) in exactly the same positions. Hence, we solve the problem

$$\begin{aligned} \mathbf{v}_{E:2}^T \left( \frac{5}{3} \, m_c \, I - \lambda \, m^2 \, M_e \right) \mathbf{v}_{E:2} = 0 \end{aligned}$$

and obtain the two-fold eigenvalue \(5/(3m^2)\) and the eigenvalue \(5/(12m^2)\), which yields the lower bound for \(\lambda _E^{\min }\). According to (8) we obtain the estimate

$$\begin{aligned} \gamma _{M,E}^2 = 1 - \lambda _E^{\min } \le 1 - \frac{5}{12 \, m^2} = \frac{12 \, m^2 - 5}{12 \, m^2}, \end{aligned}$$

which together with (7) gives the upper bound (28). \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kraus, J., Wolfmayr, M. On the robustness and optimality of algebraic multilevel methods for reaction–diffusion type problems. Comput. Visual Sci. 16, 15–32 (2013). https://doi.org/10.1007/s00791-014-0221-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00791-014-0221-z

Keywords

Search

Navigation