Nonstationary two-stage multisplitting methods for symmetric positive definite matrices

Nonstationary synchronous two-stage multisplitting methods for the solution of the symmetric positive definite linear system of equations are considered. The convergence properties of these methods are studied. Relaxed variants are also discussed. The main tool for the construction of the two-stage multisplitting and related theoretical investigation is the diagonally compensated reduction (cf. [1]).     

Bounds to eigenvalues of the Laplacian on L-shaped domain by variational methods

In this study, the bounds for eigenvalues of the Laplacian operator on an L-shaped domain are determined. By adopting some special functions in Goerisch method for lower bounds and in traditional Rayleigh–Ritz method for upper bounds, very accurate bounds to eigenvalues for the problem are obtained. Numerical results show that these functions can also be successfully used to solve the problem on the region with other reentrant angle.     

A filtering method for the interval eigenvalue problem

We consider the general problem of computing intervals that contain the real eigenvalues of interval matrices. Given an outer approximation (superset) of the real eigenvalue set of an interval matrix, we propose a filtering method that iteratively improves the approximation. Even though our method is based on a sufficient regularity condition, it is very efficient in practice and our experimental results suggest that it improves, in general, significantly the initial outer approximation. The proposed method works for general, as well as for symmetric interval matrices.     

On the sharpness of two-sided bounds for the Perron Root and of the related eigenvalue inclusion sets

The paper considers the sharpness problem for certain two-sided bounds for the Perron root of an irreducible nonnegative matrix. The results obtained are applied to prove the sharpness of the related eigenvalue inclusion sets in classes of matrices with fixed diagonal entries, bounded above deleted absolute row sums, and a partly specified irreducible sparsity pattern.     

A survey of some estimates of eigenvalues and condition numbers for certain preconditioned matrices

Eigenvalue and condition number estimates for preconditioned iteration matrices provide the information required to estimate the rate of convergence of iterative methods, such as preconditioned conjugate gradient methods. In recent years various estimates have been derived for (perturbed) modified (block) incomplete factorizations. We survey and extend some of these and derive new estimates. In particular we derive upper and lower estimates of individual eigenvalues and of condition number. This includes a discussion that the condition number of preconditioned second order elliptic difference matrices is O(h⁻¹). Some of the methods are applied to compute certain parameters involved in the computation of the preconditioner.     

An eigenvalue bound for the Laplacian of a graph

We present a lower bound for the smallest non-zero eigenvalue of the Laplacian of an undirected graph. The bound is primarily useful for graphs with small diameter.     

Diagonally implicit Runge-Kutta methods for stiff problems

Diagonally implicit Runge-Kutta methods are examined. It is shown that, for stiff problems, the methods based on the minimization of certain error functions have advantages over other methods; these functions are determined in terms of the errors for simplest model equations. Methods of orders three, four, five, and six are considered.     

Parallel block preconditioning based on SSOR and MILU

Two kinds of parallel preconditioners for the solution of large sparse linear systems which arise from the 2-D 5-point finite difference discretization of a convection-diffusion equation are introduced. The preconditioners are based on the SSOR or MILU preconditioners and can be implemented on parallel computers with distributed memories. One is the block preconditioner, in which the interface components of the coefficient matrix between blocks are ignored to attain parallelism in the forward-backward substitutions. The other is the modified block preconditioner, in which the block preconditioner is modified by taking the interface components into account. The effect of these preconditioners on the convergence of preconditioned iterative methods and timing results on the parallel computer (Cenju) are presented.     

Equivalent operator preconditioning for elliptic problems

The numerical solution of linear elliptic partial differential equations most often involves a finite element or finite difference discretization. To preserve sparsity, the arising system is normally solved using an iterative solution method, commonly a preconditioned conjugate gradient method. Preconditioning is a crucial part of such a solution process. In order to enable the solution of very large-scale systems, it is desirable that the total computational cost will be of optimal order, i.e. proportional to the degrees of freedom of the approximation used, which also induces mesh independent convergence of the iteration. This paper surveys the equivalent operator approach, which has proven to provide an efficient general framework to construct such preconditioners. Hereby one first approximates the given differential operator by some simpler differential operator, and then chooses as preconditioner the discretization of this operator for the same mesh. In this survey we give a uniform presentation of this approach, including theoretical foundation and several practically important applications for both symmetric and nonsymmetric equations and systems, and some nonlinear examples in the context of Newton linearization. Dedicated to the memory of Gene Golub for his friendly manner and for his broad interest and significant impact on numerical analysis.     

A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems

The inverse-free preconditioned Krylov subspace method of Golub and Ye [G.H. Golub, Q. Ye, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comp. 24 (2002) 312-334] is an efficient algorithm for computing a few extreme eigenvalues of the symmetric generalized eigenvalue problem. In this paper, we first present an analysis of the preconditioning strategy based on incomplete factorizations. We then extend the method by developing a block generalization for computing multiple or severely clustered eigenvalues and develop a robust black-box implementation. Numerical examples are given to illustrate the analysis and the efficiency of the block algorithm.     

A class of generalized shift-splitting preconditioners for nonsymmetric saddle point problems

In this paper, a class of generalized shift-splitting preconditioners with two shift parameters are implemented for nonsymmetric saddle point problems with nonsymmetric positive definite (1, 1) block. The generalized shift-splitting (GSS) preconditioner is induced by a generalized shift-splitting of the nonsymmetric saddle point matrix, resulting in an unconditional convergent fixed-point iteration. By removing the shift parameter in the (1, 1) block of the GSS preconditioner, a deteriorated shift-splitting (DSS) preconditioner is presented. Some useful properties of the DSS preconditioned saddle point matrix are studied. Finally, numerical experiments of a model Navier–Stokes problem are presented to show the effectiveness of the proposed preconditioners.     

Chebyshev-type methods and preconditioning techniques

Recently, a Newton’s iterative method is attracting more and more attention from various fields of science and engineering. This method is generally quadratically convergent. In this paper, some Chebyshev-type methods with the third order convergence are analyzed in detail and used to compute approximate inverse preconditioners for solving the linear system Ax = b. Theoretic analysis and numerical experiments show that Chebyshev’s method is more effective than Newton’s one in the case of constructing approximate inverse preconditioners.     

Eigenvalue bounds in the gaps of Schrödinger operators and Jacobi matrices

We consider C=A+B where A is selfadjoint with a gap (a,b) in its spectrum and B is (relatively) compact. We prove a general result allowing B of indefinite sign and apply it to obtain a (δV)^d/2 bound for perturbations of suitable periodic Schrödinger operators and a (not quite) Lieb–Thirring bound for perturbations of algebro-geometric almost periodic Jacobi matrices.     

Displacement decomposition—incomplete factorization preconditioning techniques for linear elasticity problems

Two preconditioning techniques for the numerical solution of linear elasticity problems are described and studied. Both techniques are based on spectral equivalence approach. The first technique consists in an incomplete factorization of the separate displacement component part of the stiffness matrix. The second technique uses an incomplete factorization of the isotropic approximation to the stiffness matrix. Results concerning existence, stability and efficiency of these preconditioning techniques are presented. The efficiency and robustness of the described techniques are illustrated by numerical experiments.     

Diagonally implicit general linear methods for ordinary differential equations

We investigate some classes of general linear methods withs internal andr external approximations, with stage orderq and orderp, adjacent to the class withs=r=q=p considered by Butcher. We demonstrate that interesting methods exist also ifs+1=r=q, p=q orq+1,s=r+1=q, p=q orq+1, ands=r=q, p=q+1. Examples of such methods are constructed with stability function matching theA-acceptable generalized Padé approximations to the exponential function.The work of Z. Jackiewicz was partially supported by the National Science Foundation under grant NSF DMS-9208048.     

Block preconditioning strategies for nonlinear viscous wave equations

In this paper, five block preconditioning strategies are proposed to solve a class of nonlinear viscous wave equations. Implicit time-integration techniques from low order to high order are considered exclusively including implicit Euler (IE1) method, backward differentiation formulas (BDF2, BDF3) as well as the Crank–Nicholson (CN2) scheme. The CN2 method demonstrates superior performance compared to the BDF2 scheme for the problems considered in this work. In addition, the third-order accurate BDF3 scheme is found to be the most efficient in terms of computational cost for a prescribed accuracy level. Moreover, the benefit of this scheme increases for tighter error tolerances.     

Robust AMLI methods for parabolic Crouzeix-Raviart FEM systems

For the iterative solution of linear systems of equations arising from finite element discretization of elliptic problems there exist well-established techniques to construct numerically efficient and computationally optimal preconditioners. Among those, most often preferred choices are Multigrid methods (geometric or algebraic), Algebraic MultiLevel Iteration (AMLI) methods, Domain Decomposition techniques.In this work, the method in focus is AMLI. We extend its construction and the underlying theory over to systems arising from discretizations of parabolic problems, using non-conforming finite element methods (FEM). The AMLI method is based on an approximated block two-by-two factorization of the original system matrix. A key ingredient for the efficiency of the AMLI preconditioners is the quality of the utilized block two-by-two splitting, quantified by the so-called Cauchy-Bunyakowski-Schwarz (CBS) constant, which measures the abstract angle between the two subspaces, associated with the two-by-two block splitting of the matrix.The particular choice of space discretization for the parabolic equations, used in this paper, is Crouzeix-Raviart non-conforming elements on triangular meshes. We describe a suitable splitting of the so-arising matrices and derive estimates for the associated CBS constant. The estimates are uniform with respect to discretization parameters in space and time as well as with respect to coefficient and mesh anisotropy, thus providing robustness of the method.     

Diagonally convex directed polyominoes and even trees: a bijection and related issues

We present a simple bijection between diagonally convex directed (DCD) polyominoes with n diagonals and plane trees with 2n edges in which every vertex has even degree (even trees), which specializes to a bijection between parallelogram polyominoes and full binary trees. Next we consider a natural definition of symmetry for DCD-polyominoes, even trees, ternary trees, and non-crossing trees, and show that the number of symmetric objects of a given size is the same in all four cases.     

Numerical studies on nonlinear Schrödinger equations by spectral collocation method with preconditioning

In this study, we use the spectral collocation method with preconditioning to solve various nonlinear Schrödinger equations. To reduce round-off error in spectral collocation method we use preconditioning. We study the numerical accuracy of the method. The numerical results obtained by this way have been compared with the exact solution to show the efficiency of the method.     

Moving boundary i.b.v.p.s for Schrödinger equations: Solution bounds and related results

The paper is concerned with i.b.v.p.s for Schrödinger equations, linear and nonlinear, in a straight line region with prescribed, moving boundaries, upon which (time-dependent) Dirichlet conditions are specified. Bounds, in terms of data, are obtained for the L₂ norm of the spatial derivative of the solutions, or for a measure related thereto: in the context of expanding boundaries, pointwise bounds for the solution may be inferred both in the linear case and in some nonlinear cases (e.g. the defocusing case). Asymptotic properties of the bounds for the aforementioned norm are discussed in the linear case. The methodology of the paper is based on a particular compact formula for the aforementioned norm of an arbitrary, complex-valued function whose values are assigned, as functions of time, on the assigned, moving boundaries of a straight line region. The application of the methodology to i.b.v.p.s for other p.d.e.s is discussed briefly.