Numerical analysis Iterative methods for linear systems Proposition

Schur complement method

Builds on Schur complement Block matrix Positive definite matrix

Statement

Let $A$ be an invertible real matrix. Write it in block form as $A = \begin{pmatrix} A_{II} & A_{I\Gamma} \\ A_{\Gamma I} & A_{\Gamma\Gamma} \end{pmatrix}, \qquad A_{II} = \begin{pmatrix} A_{11} & & \\ & \ddots & \\ & & A_{NN} \end{pmatrix}.$ Here the unknowns are split into interior unknowns $u_I = (u_1, \dots, u_N)$ of $N$ subdomains and interface unknowns $u_\Gamma$ . Each block $A_{jj}$ is invertible. Let $S = A_{\Gamma\Gamma} - A_{\Gamma I} A_{II}^{-1} A_{I\Gamma}$ be the Schur complement of $A_{II}$ in $A$ . Then $(u_I, u_\Gamma)$ solves $A u = f$ with $f = (f_I, f_\Gamma)$ if and only if $S u_\Gamma = f_\Gamma - A_{\Gamma I} A_{II}^{-1} f_I \quad \text{and} \quad u_j = A_{jj}^{-1} \bigl( f_j - (A_{I\Gamma} u_\Gamma)_j \bigr) \text{ for } j = 1, \dots, N.$ If $A$ is symmetric positive definite, then $S$ is symmetric positive definite.

Remarks

The equivalence is block Gaussian elimination: the first block row gives $u_I = A_{II}^{-1}(f_I - A_{I\Gamma} u_\Gamma)$ , and substituting into the second block row gives the interface equation. Since $A_{II}$ is block diagonal, every application of $A_{II}^{-1}$ splits into independent solves on the subdomains. If $A$ is symmetric positive definite, then $v^T S v = w^T A w$ for $w = (-A_{II}^{-1} A_{I\Gamma} v, v)$ , which is positive for $v \ne 0$ .

In practice one does not form $S$ . One solves the interface system by the conjugate gradient method, and each product $S v$ costs one solve with each $A_{jj}$ . Take a finite element discretization of an elliptic problem with a fixed set of subdomains. Then the condition number of $S$ grows like $h^{-1}$ in the mesh size $h$ , against $h^{-2}$ for $A$ . Preconditioners for $S$ , such as balancing domain decomposition, reduce this further.

Going deeper

For a student

This is the non-overlapping branch of domain decomposition methods, also called iterative substructuring. The Schur complement acts on interface functions like a discrete Steklov–Poincaré operator, mapping Dirichlet data on the interfaces to the jump of the normal fluxes. Its solution by a preconditioned Krylov method is the starting point of the Neumann–Neumann, BDD and FETI families.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Where this leads

1 page builds on this one.

Balancing domain decomposition

Tag	`R997ZAD141`
URI	`m2://R997ZAD141`
Kind	statement, proposition
Writing	W0 stub
MSC	65N55, 65F05, 65F10
Status	This copy of the site has no build data. Run `m2 status R997ZAD141`.
About	Domain decomposition methods, Schur complement
Uses	Schur complement, Block matrix, Positive definite matrix
Same as	Wikidata Q17103137 Wikipedia Schur complement method

Markdown · JSON · Edit on GitHub

What this page needs for W1

an inventory row: the row of the inventory that the node accounts for (0 of 1)
a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by

Balancing domain decomposition