HOME

TheInfoList



OR:

In
numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods th ...
, the Schur complement method, named after
Issai Schur Issai Schur (10 January 1875 – 10 January 1941) was a Russian mathematician who worked in Germany for most of his life. He studied at the University of Berlin. He obtained his doctorate in 1901, became lecturer in 1903 and, after a stay at th ...
, is the basic and the earliest version of non-overlapping
domain decomposition method In mathematics, numerical analysis, and numerical partial differential equations, domain decomposition methods solve a boundary value problem by splitting it into smaller boundary value problems on subdomains and iterating to coordinate the solut ...
, also called iterative substructuring. A
finite element The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical models, mathematical modeling. Typical problem areas of interest include the traditional fields of struct ...
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 In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-definite. The conjugate gradient method is often implemented as an iter ...
.


The method and implementation

Suppose we want to solve the Poisson equation :-\Delta u = f, \qquad u, _ = 0 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 ''U''1, ''U''2 and ''U''Γ be the degrees of freedom associated with each subdomain and with the interface. We can then write the linear system as :\left begin A_ & 0 & A_ \\ 0 & A_ & A_ \\ A_ & A_ & A_\end\rightleft begin U_1 \\ U_2 \\ U_\Gamma\end\right= \left begin F_1 \\ F_2 \\ F_\Gamma\end\right where ''F''1, ''F''2 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 :\Sigma U_\Gamma = F_\Gamma - A_A_^F_1 - A_A_^F_2, for the interface values ''U''Γ, where we define the ''Schur complement'' matrix :\Sigma = A_ - A_A_^A_ - A_A_^A_. The important thing to note is that the computation of any quantities involving A_^ or A_^ involves solving decoupled
Dirichlet problem In mathematics, a Dirichlet problem is the problem of finding a function which solves a specified partial differential equation (PDE) in the interior of a given region that takes prescribed values on the boundary of the region. The Dirichlet pro ...
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 :A_U_1 = F_1 - A_U_\Gamma, \qquad A_U_2 = F_2 - A_U_\Gamma, which can both be done in parallel. The multiplication of a vector by the Schur complement is a
discrete Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory *Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit *Discrete group, a ...
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 In mathematics and physics, Laplace's equation is a second-order partial differential equation named after Pierre-Simon Laplace, who first studied its properties. This is often written as \nabla^2\! f = 0 or \Delta f = 0, where \Delta = \na ...
or
linear elasticity Linear elasticity is a mathematical model of how solid objects deform and become internally stressed due to prescribed loading conditions. It is a simplification of the more general nonlinear theory of elasticity and a branch of continuum mec ...
, the matrix of the system has
condition number In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
of the order 1/''h''2, 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. When a fast function is utilized, especially in low cost parallel computers, the Schur complement method is relatively efficient.


References

{{DEFAULTSORT:Schur Complement Method Domain decomposition methods