Resolvent Krylov subspace approximation to operator functions

We consider the approximation of operator functions in resolvent Krylov subspaces. Besides many other applications, such approximations are currently of high interest for the approximation of φ-functions that arise in the numerical solution of evolution equations by exponential integrators. It is well known that Krylov subspace methods for matrix functions without exponential decay show superlinear convergence behaviour if the number of steps is larger than the norm of the operator. Thus, Krylov approximations may fail to converge for unbounded operators. In this paper, we analyse a rational Krylov subspace method which converges not only for finite element or finite difference approximations to differential operators but even for abstract, unbounded operators whose field of values lies in the left half plane. In contrast to standard Krylov methods, the convergence will be independent of the norm of the discretised operator and thus of the spatial discretisation. We will discuss efficient implementations for finite element discretisations and illustrate our analysis with numerical experiments.     

Matrix Krylov subspace methods for linear systems with multiple right-hand sides

In this paper, we first give a result which links any global Krylov method for solving linear systems with several right-hand sides to the corresponding classical Krylov method. Then, we propose a general framework for matrix Krylov subspace methods for linear systems with multiple right-hand sides. Our approach use global projection techniques, it is based on the Global Generalized Hessenberg Process (GGHP) – which use the Frobenius scalar product and construct a basis of a matrix Krylov subspace – and on the use of a Galerkin or a minimizing norm condition. To accelerate the convergence of global methods, we will introduce weighted global methods. In these methods, the GGHP uses a different scalar product at each restart. Experimental results are presented to show the good performances of the weighted global methods. AMS subject classification 65F10     

Stopping criteria for iterations in finite element methods

Summary. This work extends the results of Arioli [1], [2] on stopping criteria for iterative solution methods for linear finite element problems to the case of nonsymmetric positive-definite problems. We show that the residual measured in the norm induced by the symmetric part of the inverse of the system matrix is relevant to convergence in a finite element context. We then use Krylov solvers to provide alternative ways of calculating or estimating this quantity and present numerical experiments which validate our criteria.Mathematics Subject Classification (2000): 65N30, 65F10, 65F35     

Block Krylov Subspace Methods for Solving Large Sylvester Equations

In the present paper, we propose block Krylov subspace methods for solving the Sylvester matrix equation AX–XB=C. We first consider the case when A is large and B is of small size. We use block Krylov subspace methods such as the block Arnoldi and the block Lanczos algorithms to compute approximations to the solution of the Sylvester matrix equation. When both matrices are large and the right-hand side matrix is of small rank, we will show how to extract low-rank approximations. We give some theoretical results such as perturbation results and bounds of the norm of the error. Numerical experiments will also be given to show the effectiveness of these block methods.     

PPIFE Method with Non-Homogeneous Flux Jump Conditions and Its Efficient Numerical Solver for Elliptic Optimal Control Problems with Interfaces

In this paper, we design a partially penalized immersed finite element method for solving elliptic interface problems with non-homogeneous flux jump conditions. The method presented here has the same global degrees of freedom as classic immersed finite element method. The non-homogeneous flux jump conditions can be handled accurately by additional immersed finite element functions. Four numerical examples are provided to demonstrate the optimal convergence rates of the method in $L^{\infty}$, $L^{2}$ and $H^{1}$ norms. Furthermore, the method is combined with post-processing technique to solve elliptic optimal control problems with interfaces. To solve the resulting large-scale system, block diagonal preconditioners are introduced. These preconditioners can lead to fast convergence of the Krylov subspace methods such as GMRES and are independent of the mesh size. Four numerical examples are presented to illustrate the efficiency of the numerical schemes and preconditioners.     

Acoustic simulations with higher order finite and infinite elements

The efficiency of finite element based simulations of Helmholtz problems is primarily affected by two facts. First, the numerical solution suffers from the so-called pollution effect, which leads to very high element resolutions at higher frequencies. Furthermore, the spectral properties of the resulting system matrices, and hence the convergence of iterative solvers, deteriorate with increasing wave numbers. In this contribution the influence of different types of polynomial basis functions on the efficiency and stability of interior as well as exterior acoustic simulations is analyzed. The current investigations show that a proper choice for the polynomial shape approximation may significantly increase the performance of Krylov subspace methods. In particular, the efficiency of higher order finite and infinite elements based on Bernstein polynomial shape approximation and the corresponding iterative solution strategies is assessed for practically relevant numerical examples including the sound radiation from rolling vehicle tires. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Iterative regularization with minimum-residual methods

We study the regularization properties of iterative minimum-residual methods applied to discrete ill-posed problems. In these methods, the projection onto the underlying Krylov subspace acts as a regularizer, and the emphasis of this work is on the role played by the basis vectors of these Krylov subspaces. We provide a combination of theory and numerical examples, and our analysis confirms the experience that MINRES and MR-II can work as general regularization methods. We also demonstrate theoretically and experimentally that the same is not true, in general, for GMRES and RRGMRES – their success as regularization methods is highly problem dependent. AMS subject classification (2000)  65F22, 65F10     

Superlinear convergence of the rational Arnoldi method for the approximation of matrix functions

A superlinear convergence bound for rational Arnoldi approximations to functions of matrices is derived. This bound generalizes the well-known superlinear convergence bound for the conjugate gradient method to more general functions with finite singularities and to rational Krylov spaces. A constrained equilibrium problem from potential theory is used to characterize a max-min quotient of a nodal rational function underlying the rational Arnoldi approximation, where an additional external field is required for taking into account the poles of the rational Krylov space. The resulting convergence bound is illustrated at several numerical examples, in particular, the convergence of the extended Krylov method for the matrix square root.     

A Black-Box Multigrid Preconditioner for the Biharmonic Equation

We examine the convergence characteristics of a preconditioned Krylov subspace solver applied to the linear systems arising from low-order mixed finite element approximation of the biharmonic problem. The key feature of our approach is that the preconditioning can be realized using any “black-box” multigrid solver designed for the discrete Dirichlet Laplacian operator. This leads to preconditioned systems having an eigenvalue distribution consisting of a tightly clustered set together with a small number of outliers. Numerical results show that the performance of the methodology is competitive with that of specialized fast iteration methods that have been developed in the context of biharmonic problems. This revised version was published online in July 2006 with corrections to the Cover Date.     

On Finite-Difference Approximations for Normalized Bellman Equations

A class of stochastic optimal control problems involving optimal stopping is considered. Methods of Krylov (Appl. Math. Optim. 52(3):365–399, 2005) are adapted to investigate the numerical solutions of the corresponding normalized Bellman equations and to estimate the rate of convergence of finite difference approximations for the optimal reward functions.     

Eigenvalues of a nonlinear ground state in the Thomas-Fermi approximation

We study a nonlinear ground state of the Gross-Pitaevskii equation with a parabolic potential in the hydrodynamics limit often referred to as the Thomas-Fermi approximation. Existence of the energy minimizer has been known in literature for some time but it was only recently when the Thomas-Fermi approximation was rigorously justified. The spectrum of linearization of the Gross-Pitaevskii equation at the ground state consists of an unbounded sequence of positive eigenvalues. We analyze convergence of eigenvalues in the hydrodynamics limit. Convergence in norm of the resolvent operator is proved and the convergence rate is estimated. We also study asymptotic and numerical approximations of eigenfunctions and eigenvalues using Airy functions.     

Finite-Dimensional Approximations of Operators in the Hilbert Spaces of Functions on Locally Compact Abelian Groups

A new approach to the approximation of operators in the Hilbert space of functions on a locally compact Abelian (LCA) group is developed. This approach is based on sampling the symbols of such operators. To choose the points for sampling, we use the approximations of LCA groups by finite groups, which were introduced and investigated by Gordon. In the case of the group R ⁿ , the constructed approximations include the finite-dimensional approximations of the coordinate and linear momentum operators, suggested by Schwinger. The finite-dimensional approximations of the Schrödinger operator based on Schwinger's approximations were considered by Digernes, Varadarajan, and Varadhan in Rev. Math. Phys. 6 (4) (1994), 621–648 where the convergence of eigenvectors and eigenvalues of the approximating operators to those of the Schrödinger operator was proved in the case of a positive potential increasing at infinity. Here this result is extended to the case of Schrödinger-type operators in the Hilbert space of functions on LCA groups. We consider the approximations of p-adic Schrödinger operators as an example. For the investigation of the constructed approximations, the methods of nonstandard analysis are used.     

Polynomial representations from abstract perturbed Krylov methods

We present the framework of “abstract perturbed Krylov methods”, a new, unified point of view on different types of Krylov subspace methods. We give a brief informal sketch of polynomial representations of QOR approximations to solutions of linear systems and eigenvectors. The results are applicable to exact arithmetic, finite precision computations including semiduality approaches, and inexact methods. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Efficient and reliable iterative methods for linear systems

The approximate solutions in standard iteration methods for linear systems Ax=b, with A an n by n nonsingular matrix, form a subspace. In this subspace, one may try to construct better approximations for the solution x. This is the idea behind Krylov subspace methods. It has led to very powerful and efficient methods such as conjugate gradients, GMRES, and Bi-CGSTAB. We will give an overview of these methods and we will discuss some relevant properties from the user's perspective view.The convergence of Krylov subspace methods depends strongly on the eigenvalue distribution of A, and on the angles between eigenvectors of A. Preconditioning is a popular technique to obtain a better behaved linear system. We will briefly discuss some modern developments in preconditioning, in particular parallel preconditioners will be highlighted: reordering techniques for incomplete decompositions, domain decomposition approaches, and sparsified Schur complements.     

Balanced truncation model order reduction in limited time intervals for large systems

In this article we investigate model order reduction of large-scale systems using time-limited balanced truncation, which restricts the well known balanced truncation framework to prescribed finite time intervals. The main emphasis is on the efficient numerical realization of this model reduction approach in case of large system dimensions. We discuss numerical methods to deal with the resulting matrix exponential functions and Lyapunov equations which are solved for low-rank approximations. Our main tool for this purpose are rational Krylov subspace methods. We also discuss the eigenvalue decay and numerical rank of the solutions of the Lyapunov equations. These results, and also numerical experiments, will show that depending on the final time horizon, the numerical rank of the Lyapunov solutions in time-limited balanced truncation can be smaller compared to standard balanced truncation. In numerical experiments we test the approaches for computing low-rank factors of the involved Lyapunov solutions and illustrate that time-limited balanced truncation can generate reduced order models having a higher accuracy in the considered time region.     

On nonlinear artificial viscosity,discrete maximum principle and hyperbolic conservation laws

A finite element method for Burgers’ equation is studied. The method is analyzed using techniques from stabilized finite element methods and convergence to entropy solutions is proven under certain hypotheses on the artificial viscosity. In particular we assume that a discrete maximum principle holds. We then construct a nonlinear artificial viscosity that satisfies the assumptions required for convergence and that can be tuned to minimize artificial viscosity away from local extrema. The theoretical results are exemplified on a numerical example. AMS subject classification (2000)  65M20, 65M12, 35L65, 76M10     

On some notions of convergence for n‐tuples of operators

The aim of this paper is to show that we can extend the notion of convergence in the norm‐resolvent sense to the case of several unbounded noncommuting operators (and to quaternionic operators as a particular case) using the notion of S‐resolvent operator. With this notion, we can define bounded functions of unbounded operators using the S‐functional calculus for n‐tuples of noncommuting operators. The same notion can be extended to the case of the F‐resolvent operator, which is the basis of the F‐functional calculus, a monogenic functional calculus for n‐tuples of commuting operators. We also prove some properties of the F‐functional calculus, which are of independent interest. Copyright © 2013 John Wiley & Sons, Ltd.     

Piecewise linear least squares approximations of Frobenius-Perron operators

We propose a piecewise linear numerical method based on least squares approximations for computing stationary density functions of Frobenius-Perron operators associated with piecewise C² and stretching mappings of the unit interval. We prove the weak convergence of the method for a class of Frobenius-Perron operators, and the numerical results show that it is also norm convergent and has a better convergence rate than the piecewise linear Markov approximation method.     

Sobolev estimates for constructive uniform-grid FFT interpolatory approximations of spherical functions

The fast Fourier transform (FFT) based matrix-free ansatz interpolatory approximations of periodic functions are fundamental for efficient realization in several applications. In this work we design, analyze, and implement similar constructive interpolatory approximations of spherical functions, using samples of the unknown functions at the poles and at the uniform spherical-polar grid locations \(\left (\frac {j\pi }{N}, \frac {k \pi }{N}\right )\), for j=1,…,N?1, k=0,…,2N?1. The spherical matrix-free interpolation operator range space consists of a selective subspace of two dimensional trigonometric polynomials which are rich enough to contain all spherical polynomials of degree less than N. Using the \({\mathcal {O}}(N^{2})\) data, the spherical interpolatory approximation is efficiently constructed by applying the FFT techniques (in both azimuthal and latitudinal variables) with only \({\mathcal {O}}(N^{2} \log N)\) complexity. We describe the construction details using the FFT operators and provide complete convergence analysis of the interpolatory approximation in the Sobolev space framework that are well suited for quantification of various computer models. We prove that the rate of spectrally accurate convergence of the interpolatory approximations in Sobolev norms (of order zero and one) are similar (up to a log term) to that of the best approximation in the finite dimensional ansatz space. Efficient interpolatory quadratures on the sphere are important for several applications including radiation transport and wave propagation computer models. We use our matrix-free interpolatory approximations to construct robust FFT-based quadrature rules for a wide class of non-, mildly-, and strongly-oscillatory integrands on the sphere. We provide numerical experiments to demonstrate fast evaluation of the algorithm and various theoretical results presented in the article.     

Interpolation of functions by the least squares method

We study the norm of a best quadratic trigonometric approximation operator on a finite uniform grid. Dedicated to the memory of my scientific adviser, Professor S. B. Stechkin Translated fromMatematicheskie Zametki, Vol. 66, No. 3, pp. 372–379, September, 1999.