Schur complement method
Encyclopedia
In numerical analysis
, the Schur complement method, named after Issai Schur
, is the basic and the earliest version of non-overlapping domain decomposition method
, also called iterative substructuring. A finite element problem is split into non-overlapping subdomains, and the unknowns in the interiors of the subdomains are eliminated. The remaining Schur complement system on the unknowns associated with subdomain interfaces is solved by the conjugate gradient method
.
on some domain Ω. When we discretize this problem we get an N-dimensional linear system AU = F. The Schur complement method splits up the linear system into sub-problems. To do so, divide Ω into two subdomains Ω1, Ω2 which share an interface Γ. Let U1, U2 and UΓ be the degrees of freedom associated with each subdomain and with the interface. We can then write the linear system as
where F1, F2 and FΓ are the components of the load vector in each region.
The Schur complement method proceeds by noting that we can find the values on the interface by solving the smaller system
for the interface values UΓ, where we define the Schur complement matrix
The important thing to note is that the computation of any quantities involving
or 
involves solving decoupled Dirichlet problem
s on each domain, and these can be done in parallel. Consequently, we need not store the Schur complement matrix explicitly; it is sufficient to know how to multiply a vector by it.
Once we know the values on the interface, we can find the interior values using the two relations
which can both be done in parallel.
The multiplication of a vector by the Schur complement is a discrete
version of the Poincaré–Steklov operator, also called the Dirichlet to Neumann mapping.
, the matrix of the system has condition number
of the order 1/h2, where h is the characteristic element size. The Schur complement, however, has condition number only of the order 1/h.
For performances, the Schur complement method is combined with preconditioning, at least a diagonal preconditioner. The Neumann–Neumann method and the Neumann–Dirichlet method are the Schur complement method with particular kinds of preconditioners.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, the Schur complement method, named after Issai Schur
Issai Schur
Issai Schur was a mathematician who worked in Germany for most of his life. He studied at Berlin...
, is the basic and the earliest version of non-overlapping domain decomposition method
Domain decomposition method
In mathematics, the additive Schwarz method, named after Hermann Schwarz, solves a boundary value problem for a partial differential equation approximately by splitting it into boundary value problems on smaller domains and adding the results.- Overview :...
, also called iterative substructuring. A finite element problem is split into non-overlapping subdomains, and the unknowns in the interiors of the subdomains are eliminated. The remaining Schur complement system on the unknowns associated with subdomain interfaces is solved by the conjugate gradient method
Conjugate gradient method
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is symmetric and positive-definite. The conjugate gradient method is an iterative method, so it can be applied to sparse systems that are too...
.
The method and implementation
Suppose we want to solve the Poisson equationon some domain Ω. When we discretize this problem we get an N-dimensional linear system AU = F. The Schur complement method splits up the linear system into sub-problems. To do so, divide Ω into two subdomains Ω1, Ω2 which share an interface Γ. Let U1, U2 and UΓ be the degrees of freedom associated with each subdomain and with the interface. We can then write the linear system as
where F1, F2 and FΓ are the components of the load vector in each region.
The Schur complement method proceeds by noting that we can find the values on the interface by solving the smaller system
for the interface values UΓ, where we define the Schur complement matrix
The important thing to note is that the computation of any quantities involving
or involves solving decoupled Dirichlet problemDirichlet problem
In mathematics, a Dirichlet problem is the problem of finding a function which solves a specified partial differential equation in the interior of a given region that takes prescribed values on the boundary of the region....
s on each domain, and these can be done in parallel. Consequently, we need not store the Schur complement matrix explicitly; it is sufficient to know how to multiply a vector by it.
Once we know the values on the interface, we can find the interior values using the two relations
which can both be done in parallel.
The multiplication of a vector by the Schur complement is a discrete
Discretization
In mathematics, discretization concerns the process of transferring continuous models and equations into discrete counterparts. This process is usually carried out as a first step toward making them suitable for numerical evaluation and implementation on digital computers...
version of the Poincaré–Steklov operator, also called the Dirichlet to Neumann mapping.
Advantages
There are two benefits of this method. First, the elimination of the interior unknowns on the subdomains, that is the solution of the Dirichlet problems, can be done in parallel. Second, passing to the Schur complement reduces condition number and thus tends to decrease the number of iterations. For second-order problems, such as the Laplace equation or linear elasticityLinear elasticity
Linear elasticity is the mathematical study of how solid objects deform and become internally stressed due to prescribed loading conditions. Linear elasticity models materials as continua. Linear elasticity is a simplification of the more general nonlinear theory of elasticity and is a branch of...
, the matrix of the system has condition number
Condition number
In the field of numerical analysis, the condition number of a function with respect to an argument measures the asymptotically worst case of how much the function can change in proportion to small changes in the argument...
of the order 1/h2, where h is the characteristic element size. The Schur complement, however, has condition number only of the order 1/h.
For performances, the Schur complement method is combined with preconditioning, at least a diagonal preconditioner. The Neumann–Neumann method and the Neumann–Dirichlet method are the Schur complement method with particular kinds of preconditioners.