On the construction of restricted-denominator exponential W-methods

In this paper we consider the practical construction of exponential W-methods for the solution of large stiff nonlinear initial value problems, based on the restricted-denominator rational approach for the computation of the functions of matrices required. This approach is employed together with the Krylov subspace method based on the Arnoldi algorithm. Two integrators are constructed and tested on some classical stiff equations arising from the semidiscretization of parabolic problems.     

A posteriori estimates of inverse operators for initial value problems in linear ordinary differential equations

We present constructive a posteriori estimates of inverse operators for initial value problems in linear ordinary differential equations (ODEs) on a bounded interval. Here, “constructive” indicates that we can obtain bounds of the operator norm in which all constants are explicitly given or are represented in a numerically computable form. In general, it is difficult to estimate these inverse operators a priori. We, therefore, propose a technique for obtaining a posteriori estimates by using Galerkin approximation of inverse operators. This type of estimation will play an important role in the numerical verification of solutions for initial value problems in nonlinear ODEs as well as for parabolic initial boundary value problems.     

Trimmed linearizations for structured matrix polynomials

We discuss the eigenvalue problem for general and structured matrix polynomials which may be singular and may have eigenvalues at infinity. We derive condensed forms that allow (partial) deflation of the infinite eigenvalue and singular structure of the matrix polynomial. The remaining reduced order staircase form leads to new types of linearizations which determine the finite eigenvalues and corresponding eigenvectors. The new linearizations also simplify the construction of structure preserving linearizations.     

A method for approximation of the exponential map in semidirect product of matrix Lie groups and some applications

In this paper we explore the computation of the matrix exponential in a manner that is consistent with Lie group structure. Our point of departure is the decomposition of Lie algebra as the semidirect product of two Lie subspaces and an application of the Baker-Campbell-Hausdorff formula. Our results extend the results in Iserles and Zanna (2005) [2], Zanna and Munthe-Kaas(2001/02) [4] to a range of Lie groups: the Lie group of all solid motions in Euclidean space, the Lorentz Lie group of all solid motions in Minkowski space and the group of all invertible (upper) triangular matrices. In our method, the matrix exponential group can be computed by a less computational cost and is more accurate than the current methods. In addition, by this method the approximated matrix exponential belongs to the corresponding Lie group.     

Constrained least squares methods for linear timevarying DAE systems

Summary This paper presents a family of methods for accurate solution of higher index linear variable DAE systems, . These methods use the DAE system and some of its first derivatives as constraints to a least squares problem that corresponds to a Taylor series ofy, or an approximative equality derived from a Pade' approximation of the exponential function. Accuracy results for systems transformable to standard canonical form are given. Advantages, disadvantages, stability properties and implementation of these methods are discussed and two numerical examples are given, where we compare our results with results from more traditional methods.     

On the convergence of splittings for semidefinite linear systems

Recently, Lee et al. [Young-ju Lee, Jinbiao Wu, Jinchao Xu, Ludmil Zikatanov, On the convergence of iterative methods for semidefinite linear systems, SIAM J. Matrix Anal. Appl. 28 (2006) 634-641] introduce new criteria for the semi-convergence of general iterative methods for semidefinite linear systems based on matrix splitting. The new conditions generalize the classical notion of P-regularity introduced by Keller [H.B. Keller, On the solution of singular and semidefinite linear systems by iterations, SIAM J. Numer. Anal. 2 (1965) 281-290]. In view of their results, we consider here stipulations on a splitting A=M-N, which lead to fixed point systems such that, the iterative scheme converges to a weighted Moore-Penrose solution to the system Ax=b. Our results extend the result of Lee et al. to a more general case and we also show that it requires less restrictions on the splittings than Keller’s P-regularity condition to ensure the convergence of iterative scheme.     

Fast inversion of vandermonde-like matrices involving orthogonal polynomials

Let {q} _j ^=0n–1 be a family of polynomials that satisfy a three-term recurrence relation and let {t _k } _k ⁼¹ⁿ be a set of distinct nodes. Define the Vandermonde-like matrixW _n =[w _jk ] _k,j ⁼¹ⁿ ,w _jk =q _j–1(t _k ). We describe a fast algorithm for computing the elements of the inverse ofW _n inO(n ²) arithmetic operations. Our algorithm generalizes a scheme presented by Traub [22] for fast inversion of Vandermonde matrices. Numerical examples show that our scheme often yields higher accuracy than the LINPACK subroutine SGEDI for inverting a general matrix. SGEDI uses Gaussian elimination with partial pivoting and requiresO(n ³) arithmetic operations.Dedicated to Gene H. Golub on his 60th birthdayResearch supported by NSF grant DMS-9002884.     

Comparison theorems for weak splittings of bounded operators

Summary Comparison theorems for weak splittings of bounded operators are presented. These theorems extend the classical comparison theorem for regular splittings of matrices by Varga, the less known result by Wonicki, and the recent results for regular and weak regular splittings of matrices by Neumann and Plemmons, Elsner, and Lanzkron, Rose and Szyld. The hypotheses of the theorems presented here are weaker and the theorems hold for general Banach spaces and rather general cones. Hypotheses are given which provide strict inequalities for the comparisons. It is also shown that the comparison theorem by Alefeld and Volkmann applies exclusively to monotone sequences of iterates and is not equivalent to the comparison of the spectral radius of the iteration operators.This work was supported by the National Science Foundation grants DMS-8807338 and INT-8918502     

A class of explicit multistep exponential integrators for semilinear problems

A class of explicit multistep exponential methods for abstract semilinear equations is introduced and analyzed. It is shown that the k-step method achieves order k, for appropriate starting values, which can be computed by auxiliary routines or by one strategy proposed in the paper. Together with some implementation issues, numerical illustrations are also provided.     

Two different approaches for matching nonconforming grids: The Mortar Element method and the Feti Method

When using domain decomposition in a finite element framework for the approximation of second order elliptic or parabolic type problems, it has become appealing to tune the mesh of each subdomain to the local behaviour of the solution. The resulting discretization being then nonconforming, different approaches have been advocated to match the admissible discrete functions. We recall here the basics of two of them, the Mortar Element method and the Finite Element Tearing and Interconnecting (FETI) method, and aim at comparing them. The conclusion, both from the theoretical and numerical point of view, is in favor of the mortar element method.     

Real pole approximations to the exponential function

Rational approximations to the exponential function with real, not necessarily distinct poles are studied in this paper. The orthogonality relation is established in order to show that the zeros of the collocation polynomial of the corresponding Runge-Kutta method are all real, simple and positive. It is proven, that approximants with the smallest error constant are the Restricted Padé approximants of Nørsett. Some results concerning acceptability properties are given.This work was supported by RSS, Ljubljana while the author was at Division of Mathematical Sciences, Norwegian Institute of Technology, Trondheim.     

Finite sections for singular integral operators by weighted Chebyshev polynomials

A finite section method for the approximate solution of singular integral equations with piecewise continuous coefficients on intervals is considered. The problem is transformed in such a way that results which were previously obtained for singular integral equations on the unit circle using localization methods in Banach algebras are applicable to it. Thus, necessary and sufficient conditions for the stability of the approximation method can be proved.     

Singular-value-like decomposition for complex matrix triples

The classical singular value decomposition for a matrix A∈C^m×n is a canonical form for A that also displays the eigenvalues of the Hermitian matrices AA^∗ and A^∗A. In this paper, we develop a corresponding decomposition for A that provides the Jordan canonical forms for the complex symmetric matrices and . More generally, we consider the matrix triple , where are invertible and either complex symmetric or complex skew-symmetric, and we provide a canonical form under transformations of the form , where X,Y are nonsingular.     

Remarks on Picard-Lindelöf iteration

The paper discusses Picard-Lindelöf iteration for systems of autonomous linear equations on finite intervals, as well as its numerical variants. Most of the discussion is under a model assumption which roughly says that the coupling terms are of moderate size compared with the slow time scales in the problem. It is shown that the speed of convergence is quite independent of the step sizes already for very large time steps. This makes it possible to design strategies in which the mesh gets gradually refined during the iteration in such a way that the iteration error stays essentially on the level of discretization error.This research was supported by the Academy of Finland and by the Institute for Mathematics and its Applications (IMA, Minneapolis with funds provided by NSF). Ulla Miekkala visited IMA with a grant from Tekniikan edisstämissäätiö and carried out the numerical tests.     

Preconditioned CG-type methods for solving the coupled system of fundamental semiconductor equations

This paper presents some of the authors' experimental results in applying Preconditioned CG-type methods to nonsymmetric systems of linear equations arising in the numerical solution of the coupled system of fundamental stationary semiconductor equations. For this type of problem it is shown that these iterative methods are efficient both in computation times and in storage requirements. All results have been obtained on an HP 350 computer.     

Numerical computation of an analytic singular value decomposition of a matrix valued function

Summary This paper extends the singular value decomposition to a path of matricesE(t). An analytic singular value decomposition of a path of matricesE(t) is an analytic path of factorizationsE(t)=X(t)S(t)Y(t) ^T whereX(t) andY(t) are orthogonal andS(t) is diagonal. To maintain differentiability the diagonal entries ofS(t) are allowed to be either positive or negative and to appear in any order. This paper investigates existence and uniqueness of analytic SVD's and develops an algorithm for computing them. We show that a real analytic pathE(t) always admits a real analytic SVD, a full-rank, smooth pathE(t) with distinct singular values admits a smooth SVD. We derive a differential equation for the left factor, develop Euler-like and extrapolated Euler-like numerical methods for approximating an analytic SVD and prove that the Euler-like method converges.Partial support received from SFB 343, Diskrete Strukturen in der Mathematik, Universität BielefeldPartial support received from FSP Mathematisierung, Universität BielefeldPartial support received from FSP Mathematisierung, Universität BielefeldPartial support received from National Science Foundation grant CCR-8820882. Some support was also received from the University of Kansas through International Travel Fund 560478 and General Research Allocations # 3758-20-0038 and #3692-20-0038.     

Preconditionings and splittings for rectangular systems

Summary Recently Eiermann, Marek, and Niethammer have shown how to applysemiiterative methods to a fixed point systemx=Tx+c which isinconsistent or in whichthe powers of the fixed point operator T have no limit, to obtain iterative methods which converge to some approximate solution to the fixed point system. In view of their results we consider here stipulations on apreconditioning QAx=Qb of the systemAx=b and, separately, on asplitting A=M–N which lead to fixed point systems such that, with the aid of a semiiterative method, the iterative scheme converges to a weighted Moore-Penrose solution to the systemAx=b. We show in several ways that to obtain a meaningful limit point from a semiiterative method requires less restrictions on the splittings or the reconditionings than those which have been required in the classical Picard iterative method (see, e.g., the works of Berman and Plemmons, Berman and Neumann, and Tanabe).We pay special attention to the case when the weighted Moore-Penrose solution which is sought is the minimal norm least squares solution toAx=b.Research supported by the Deutsche ForschungsgemeinschaftPartially supported by AFOSR research grant 88-0047     

Fibred coarse embeddings,a-T-menability and the coarse analogue of the Novikov conjecture

The connection between the coarse geometry of metric spaces and analytic properties of topological groupoids is well known. One of the main results of Skandalis, Tu and Yu is that a space admits a coarse embedding into Hilbert space if and only if a certain associated topological groupoid is a-T-menable. This groupoid characterisation then reduces the proof that the coarse Baum–Connes conjecture holds for a coarsely embeddable space to known results for a-T-menable groupoids. The property of admitting a fibred coarse embedding into Hilbert space was introduced by Chen, Wang and Yu to provide a property that is sufficient for the maximal analogue to the coarse Baum–Connes conjecture and in this paper we connect this property to the traditional coarse Baum–Connes conjecture using a restriction of the coarse groupoid and homological algebra. Additionally we use this results to give a characterisation of the a-T-menability for residually finite discrete groups.