112,312 research outputs found
The behavior of symmetric Krylov subspace methods for solving Mx=(M−γI)v
No full textAbstractWe analyze the behavior of Krylov subspace methods for the solution of the symmetric system Mx=(M−γI)v when γ is close to some of the extreme eigenvalues of M. We show that a stagnation phase may occur if the structure of the right-hand side is not taken into account, and we analyze the occurrence and persistence of such stagnation. A natural alternative strategy is proposed and we show that the new approach provides a better approximation, with the same number of matrix–vector multiplications. Numerical experiments are also included
Numerical solution of a class of third order tensor linear equations
No full textWe propose a new dense method for determining the numerical solution to a class of third order tensor linear equations. The approach does not require the use of the coefficient matrix in Kronecker form, thus it allows the treatment of structured very large problems. A particular version of the method for symmetric matrices is also discussed. Numerical experiments illustrate the properties of the proposed algorithm
A numerical solution of a Cauchy problem for an elliptic equation by Krylov subspaces
No full textWe study the numerical solution of a Cauchy problem for a self-adjoint elliptic partial differential equation u(zz) - L-u = 0 in three space dimensions (x, y, z), where the domain is cylindrical in z. Cauchy data are given on the lower boundary and the boundary values on the upper boundary are sought. The problem is severely ill-posed. The formal solution is written as a hyperbolic cosine function in terms of the two-dimensional elliptic operator L (via its eigenfunction expansion), and it is shown that the solution is stabilized (regularized) if the large eigenvalues are cut off. We suggest a numerical procedure based on the rational Krylov method, where the solution is projected onto a subspace generated using the operator L-1. This means that in each Krylov step, a well-posed two-dimensional elliptic problem involving L is solved. Furthermore, the hyperbolic cosine is evaluated explicitly only for a small symmetric matrix. A stopping criterion for the Krylov recursion is suggested based on the relative change of an approximate residual, which can be computed very cheaply. Two numerical examples are given that demonstrate the accuracy of the method and the efficiency of the stopping criterion.Original Publication:Lars Eldén and Valeria Simoncini, A numerical solution of a Cauchy problem for an elliptic equation by Krylov subspaces, 2009, INVERSE PROBLEMS, (25), 6, 065002.http://dx.doi.org/10.1088/0266-5611/25/6/065002Copyright: Iop Publishing Ltdhttp://www.iop.org
Analysis of projection methods for rational function approximation to the matrix exponential
No full textKrylov subspace methods for approximating the action of the matrix exponential
exp(A) on a vector v are analyzed with A Hermitian and negative semidefinite. Our approach is
based on approximating the exponential with the commonly employed diagonal Pad ́e and Chebyshev
rational functions, which yield a system of equations with a polynomial coefficient matrix. We
derive optimality properties and error bounds for the convergence of a Galerkin-type approximation
and of a computationally feasible and extensively used alternative. As complementary results, we
theoretically justify the use of a popular a posteriori error estimate, and we provide upper bounds
for the components of the solution vector. Our theoretical and numerical results show that this
methodology may provide an appropriate framework to devise new strategies such as more powerful
acceleration schemes
On the numerical solution of a class of systems of linear matrix equations
No full textWe consider the solution of systems of linear matrix equations in two or three unknown matrices. For dense problems we derive algorithms that determine the numerical solution by only involving matrices of the same size as those in the original problem, thus requiring low computational resources. For large and structured systems we show how the problem properties can be exploited to design effective algorithms with low memory and operation requirements. Numerical experiments illustrate the performance of the new methods
A new investigation of the extended Krylov subspace method for matrix function evaluations
No full textAbstract. For large square matrices A and functions f, the numerical approximation of the action of f(A) to a vector v has received considerable attention in the last two decades. In this paper we investigate the Extended Krylov subspace method, a technique that was recently proposed to approximate f(A)v for A symmetric. We provide a new theoretical analysis of the method, which improves the original result for A symmetric, and gives a new estimate for A nonsymmetric. Numerical experiments confirm that the new error estimates correctly capture the linear asymptotic convergence rate of the approximation. By using recent algorithmic improvements, we also show that the method is computationally competitive with respect to other enhancement techniques
Preserving geometric properties of the exponential matrix by block Krylov subspaces methods
No full textGiven a large square real matrix A and a rectangular tall matrix Q, many application
problems require the approximation of the operation exp(A)Q. Under certain
hypotheses on A, the matrix exp(A)Q preserves the orthogonality characteristics of
Q; this property is particularly attractive when the associated application problem
requires some geometric constraints to be satis ̄ed. For small size problems numerical
methods have been devised to approximate exp(A)Q while maintaining the structure
properties. On the other hand, no algorithm for large A has been derived with similar
preservation properties. In this paper we show that an appropriate use of the
block Lanczos method allows one to obtain a structure preserving approximation to
exp(A)Q when A is skew-symmetric or skew-symmetric and Hamiltonian. Moreover,
for A Hamiltonian we derive a new variant of the block Lanczos method that again
preserves the geometric properties of the exact scheme. Numerical results are reported
to support our theoretical ̄ndings, with particular attention to the numerical solution
of linear dynamical systems by means of structure preserving integrators
Order Reduction Approaches for the Algebraic Riccati Equation and the LQR Problem
No full textWe explore order reduction techniques to solve the algebraic Riccati equation (ARE), and investigate the numerical solution of the linear-quadratic regulator problem (LQR). A classical approach is to build a low dimensional surrogate model of the dynamical system, for instance by means of balanced truncation, and then solve the corresponding ARE. Alternatively, iterative methods can be used to directly solve the ARE and use its approximate solution to estimate quantities associated with the LQR. We propose a class of Petrov-Galerkin strategies based on Krylov subspaces that simultaneously reduce the dynamical system while approximately solving the ARE by projection. This methodology significantly generalizes a recently developed Galerkin method, based on Krylov subspaces, by using a pair of projection spaces, as it is often done in model order reduction (MOR) of dynamical systems. Numerical experiments illustrate the advantages of the new class of methods over classical approaches when dealing with large matrices
- …
