Remarks on the Schur complement

First, a generalization of the Schur determinantal formula is given. Using properties of quasidirect sums of matrices, a new characterization of the Schur complement is proved.     

Manifestations of the Schur complement

This expository paper describes the ways in which a matrix theoretic construct called the Schur complement arises. Properties of the Schur complement are shown to have use in computing inertias of matrices, covariance matrices of conditional distributions, and other information of interest.     

Schur complement preconditioners for anisotropic problems

We present two new variants of Schur complement domain decompositionpreconditioners suitable for 2D anisotropic problems. Thesevariants are based on adaptations of the probing idea, describedby Chan et al (1992 Fifth Int. Symp. on Domain DecompositionMethods for Partial Differential Equations, Philadelphia: SIAM,pp 236-249), used in conjunction with a coarse grid approximationas introduced by Bramble et al (1986 Math. Comput. 47, 103-134).The new methods are specifically designed for situations wherethe coupling between neighbouring interfaces is stronger thanthe coupling within an interface. Taking into account this strongcoupling, one variant uses a multicolour probing technique toavoid distortion in the probe approximations that appear whenusing the method proposed by Chan et al. The second techniqueuses additional probe matrices to approximate not only the couplingwithin the interfaces but also the coupling between interfacepoints across the subdomains. This latter procedure looks somewhatlike an alternating line relaxation method for anisotropic problems,see Brandt (1977 Math. Comput.. 31, 333-390). To assess therelevance of the new preconditioners, we compare their numericalbehaviour with well known robust preconditioners such as thebalanced Neumann-Neumann method proposed by Mandel (1993 Commun.Numer. Methods Eng.. 9, 233-241).     

Inners and Schur complement

It is shown that for any square matrix having a left triangle of zeros, the determinants of its inners are equal to the leading principal minors of its Schur complement. In particular, if the original matrix has Sylvester-type form, then relationship between zero location theorems for polynomials are recovered.     

On manifestations of the Schur complement

Milan Journal of Mathematics - In this paper the author is concerned with some of the ways in which the Schur complement can be used in numerical linear algebra. Variable elimination and block...     

Using Schur complement for realtime automotive applications

Realtime simulation of stiff physical models of mechatronic systems within electronic control unit software functions poses amongst others the challenge to solve linear systems of equations with minimal comutational effort. For this, one key approach is exploiting the model structure. In this paper, Schur complement based reformulations are examined for a tailored exploitation of the sparsity of a pipe model on the level of linear equations. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On element-by-element Schur complement approximations

We discuss a methodology to construct sparse approximations of Schur complements of two-by-two block matrices arising in Finite Element discretizations of partial differential equations. Earlier results from [2] are extended to more general symmetric positive definite matrices of two-by-two block form. The applicability of the method for general symmetric and nonsymmetric matrices is analysed. The paper demonstrates the applicability of the presented method providing extensive numerical experiments.     

Block Krylov–Schur method for large symmetric eigenvalue problems

Stewart’s Krylov–Schur algorithm offers two advantages over Sorensen’s implicitly restarted Arnoldi (IRA) algorithm. The first is ease of deflation of converged Ritz vectors, the second is the avoidance of the potential forward instability of the QR algorithm. In this paper we develop a block version of the Krylov–Schur algorithm for symmetric eigenproblems. Details of this block algorithm are discussed, including how to handle rank deficient cases and how to use varying block sizes. Numerical results on the efficiency of the block Krylov–Schur method are reported.     

An asymptotically optimal Schur complement reduction for the Stokes equation

Summary. In this paper we develop an efficient Schur complement method for solving the 2D Stokes equation. As a basic algorithm, we apply a decomposition approach with respect to the trace of the pressure. The alternative stream function-vorticity reduction is also discussed. The original problem is reduced to solving the equivalent boundary (interface) equation with symmetric and positive definite operator in the appropriate trace space. We apply a mixed finite element approximation to the interface operator by iso triangular elements and prove the optimal error estimates in the presence of stabilizing bubble functions. The norm equivalences for the corresponding discrete operators are established. Then we propose an asymptotically optimal compression technique for the related stiffness matrix (in the absence of bubble functions) providing a sparse factorized approximation to the Schur complement. In this case, the algorithm is shown to have an optimal complexity of the order , q = 2 or q = 3, depending on the geometry, where N is the number of degrees of freedom on the interface. In the presence of bubble functions, our method has the complexity arithmetical operations. The Schur complement interface equation is resolved by the PCG iterations with an optimal preconditioner. Received March 20, 1996 / Revised version received October 28, 1997     

Robust Schur complement method for strongly anisotropic elliptic equations

We present robust and asymptotically optimal iterative methods for solving 2D anisotropic elliptic equations with strongly jumping coefficients, where the direction of anisotropy may change sharply between adjacent subdomains. The idea of a stable preconditioning for the Schur complement matrix is based on the use of an exotic non‐conformal coarse mesh space and on a special clustering of the edge space components according to the anisotropy behavior. Our method extends the well known BPS interface preconditioner [2] to the case of anisotropic equations. The technique proposed also provides robust solvers for isotropic equations in the presence of degenerate geometries, in particular, in domains composed of thin substructures. Numerical experiments confirm efficiency and robustness of the algorithms for the complicated problems with strongly varying diffusion and anisotropy coefficients as well as for the isotropic diffusion equations in the ‘brick and mortar’ structures involving subdomains with high aspect ratios. Copyright © 1999 John Wiley & Sons, Ltd.     

Hierarchical Schur complement preconditioner for the stochastic Galerkin finite element methods

Use of the stochastic Galerkin finite element methods leads to large systems of linear equations obtained by the discretization of tensor product solution spaces along their spatial and stochastic dimensions. These systems are typically solved iteratively by a Krylov subspace method. We propose a preconditioner, which takes an advantage of the recursive hierarchy in the structure of the global matrices. In particular, the matrices posses a recursive hierarchical two‐by‐two structure, with one of the submatrices block diagonal. Each of the diagonal blocks in this submatrix is closely related to the deterministic mean‐value problem, and the action of its inverse is in the implementation approximated by inner loops of Krylov iterations. Thus, our hierarchical Schur complement preconditioner combines, on each level in the approximation of the hierarchical structure of the global matrix, the idea of Schur complement with loops for a number of mutually independent inner Krylov iterations, and several matrix–vector multiplications for the off‐diagonal blocks. Neither the global matrix nor the matrix of the preconditioner need to be formed explicitly. The ingredients include only the number of stiffness matrices from the truncated Karhunen–Loève expansion and a good preconditioned for the mean‐value deterministic problem. We provide a condition number bound for a model elliptic problem, and the performance of the method is illustrated by numerical experiments. Copyright © 2013 John Wiley & Sons, Ltd.     

A preconditioning technique for Schur complement systems arising in stochastic optimization

Deterministic sample average approximations of stochastic programming problems with recourse are suitable for a scenario-based parallelization. In this paper the parallelization is obtained by using an interior-point method and a Schur complement mechanism for the interior-point linear systems. However, the direct linear solves involving the dense Schur complement matrix are expensive, and adversely affect the scalability of this approach. We address this issue by proposing a stochastic preconditioner for the Schur complement matrix and by using Krylov iterative methods for the solution of the dense linear systems. The stochastic preconditioner is built based on a subset of existing scenarios and can be assembled and factorized on a separate process before the computation of the Schur complement matrix finishes on the remaining processes. The expensive factorization of the Schur complement is removed from the parallel execution flow and the scaling of the optimization solver is considerably improved with this approach. The spectral analysis indicates an exponentially fast convergence in probability to 1 of the eigenvalues of the preconditioned matrix with the number of scenarios incorporated in the preconditioner. Numerical experiments performed on the relaxation of a unit commitment problem show good performance, in terms of both the accuracy of the solution and the execution time.     

On block diagonal and Schur complement preconditioning

Summary We study symmetric positive definite linear systems, with a 2-by-2 block matrix preconditioned by inverting directly one of the diagonal blocks and suitably preconditioning the other. Using an approximate version of Young's Property A, we show that the condition number of the Schur complement is smaller than the condition number obtained by the block-diagonal preconditioning. We also get bounds on both condition numbers from a strengthened Cauchy inequality. For systems arising from the finite element method, the bounds do not depend on the number of elements and can be obtained from element-by-element computations. The results are applied to thep-version finite element method, where the first block of variables consists of degrees of freedom of a low order.The research reported here was supported by the National Science Foundation under grant DMS-8704169.     

Exclusion sets in eigenvalue localization sets for tensors

ABSTRACT

By excluding some proper subsets, which do not include any eigenvalues of tensors, from an existing eigenvalue localization set provided by Zhao and Sang, a new eigenvalue localization set for tensors is given. As an application, a sufficient condition such that the determinant of a tensor is not zero is provided.     

The condition number of the Schur complement in domain decomposition

Summary. It is shown that for elliptic boundary value problems of order 2m the condition number of the Schur complement matrix that appears in nonoverlapping domain decomposition methods is of order , where d measures the diameters of the subdomains and h is the mesh size of the triangulation. The result holds for both conforming and nonconforming finite elements. Received: January 15, 1998     

On the Schur complement and the LU-factorization of a matrix

Further to a paper by Cottle [12] we discuss how the Lu-factorization of a matrix could be used to study its Schur complements and vice-versa. In addition, it is argued that the Schur complement provides a compact tool for studying problems rekated to the incomplete Choleski factorization.     

On the Schur complement and the LU-factorization of a matrix

Further to a paper by Cottle [12] we discuss how the Lu-factorization of a matrix could be used to study its Schur complements and vice-versa. In addition, it is argued that the Schur complement provides a compact tool for studying problems rekated to the incomplete Choleski factorization.     

The eigenvalue distribution on Schur complements of H-matrices

The paper studies the eigenvalue distribution of some special matrices. Tong in Theorem 1.2 of [Wen-ting Tong, On the distribution of eigenvalues of some matrices, Acta Math. Sinica (China), 20 (4) (1977) 273-275] gives conditions for an n × n matrix A ∈ SD_n ∪ ID_n to have |J_R+(A)| eigenvalues with positive real part, and |J_R-(A)| eigenvalues with negative real part. A counter-example is given in this paper to show that the conditions of the theorem are not true. A corrected condition is then proposed under which the conclusion of the theorem holds. Then the corrected condition is applied to establish some results about the eigenvalue distribution of the Schur complements of H-matrices with complex diagonal entries. Several conditions on the n × n matrix A and the subset α ⊆ N = {1, 2, … , n} are presented such that the Schur complement matrix A/α of the matrix A has eigenvalues with positive real part and eigenvalues with negative real part.     

Numerical methods for palindromic eigenvalue problems: Computing the anti‐triangular Schur form

We present structure‐preserving numerical methods for the eigenvalue problem of complex palindromic pencils. Such problems arise in control theory, as well as from palindromic linearizations of higher degree palindromic matrix polynomials. A key ingredient of these methods is the development of an appropriate condensed form—the anti‐triangular Schur form. Ill‐conditioned problems with eigenvalues near the unit circle, in particular near ±1, are discussed. We show how a combination of unstructured methods followed by a structured refinement can be used to solve such problems accurately. Copyright © 2008 John Wiley & Sons, Ltd.