1,271 research outputs found
Numerical methods for large-scale Lyapunov equations with symmetric banded data
No full text<p>This Matlab code solves a large-scale Lyapunov matrix equation with SPD banded ill-conditioned coeff. matrix and banded right-hand side by the algorith called lyap_banded.</p>
<p>test_LB.m is an example of how to call the function Lyap_Banded.m.</p>
<p>The mex files TruncSubGen_mex.mexa64 and lowrank_normF.mexa64 are necessary when calling Lyap_Banded.m and they make use of LAPACK and C-BLAS subroutines.</p>
<p>The code does not include any checking of the input data.</p>
<p>Related manuscript:</p>
<p><a href="http://www.dm.unibo.it/~davide.palitta3/">Davide Palitta</a> and <a href="http://www.dm.unibo.it/~simoncin/">Valeria Simoncini</a><br>
NUMERICAL METHODS FOR LARGE-SCALE LYAPUNOV EQUATIONS WITH SYMMETRIC BANDED DATA<br>
To appear in SISC (<a href="https://arxiv.org/pdf/1711.04187.pdf">ArXiv: 1711.04187</a>) <br>
</p>
Computationally enhanced projection methods for symmetric Sylvester and Lyapunov matrix equations
No full text<p>These Matlab codes iteratively solve large-scale Sylvester and Lyapunov matrix equations with symmetric coeff. matrix by means of the standard Krylov method with Galerkin condition (low CPU and memory requirements). Version 1.0.</p>
<p>Computational routines for Lyapunov eqs: SKSM_cTri.m, cTri.mexa64</p>
<p>example_SKSM_cTri.m is an example of how to call the function SKSM_cTri.m. </p>
<p>Computational routines for Sylvester eqs: SKSM_Sylv_cTri.m, lapack.mexa64, eig_dstevr.m, tridiag_dsbtrd.m.</p>
<p>example_SKSM_Sylv_cTri.m is an example of how to call the function SKSM_Sylv_cTri.m.</p>
<p>Notice that the mex files cTri.mexa64 and lapack.mexa64 make use of LAPACK and C-BLAS subroutines.</p>
<p>The code does not include any checking of the input data.</p>
<p>Related manuscript:</p>
<p><a href="http://www.dm.unibo.it/~davide.palitta3/">Davide Palitta</a> and <a href="http://www.google.com/url?q=http%3A%2F%2Fwww.dm.unibo.it%2F~simoncin%2F&sa=D&sntz=1&usg=AFQjCNHmany7PkUC89gQ0bQw3k3wdrPYSQ">Valeria Simoncini</a>, <a href="http://www.google.com/url?q=http%3A%2F%2Fwww.sciencedirect.com%2Fscience%2Farticle%2Fpii%2FS0377042717304004%3Fvia%253Dihub&sa=D&sntz=1&usg=AFQjCNFUqbihWZvqNfC5Y0FIwopCgf3Nlw">Computationally enhanced projection methods for symmetric Sylvester and Lyapunov matrix equations</a>.</p>REMARK: A new version of this routines can be found at https://zenodo.org/record/3252320#.XUkybk5fhu
Solving rank-structured Sylvester and Lyapunov equations
No full textWe consider the problem of efficiently solving Sylvester and Lyapunov equations of medium and large scale, in case of rank-structured data, i.e., when the coefficient matrices and the right-hand side have low-rank off-diagonal blocks. This comprises problems with banded data, recently studied in [A. Haber and M. Verhaegen, Automatica J. IFAC, 73 (2016), pp. 256-268; D. Palitta and V. Simoncini, Numerical Methods for Large-Scale Lyapunov Equations with Symmetric Banded Data, preprint, arxiv, 1711.04187, 2017], which often arise in the discretization of elliptic PDEs. We show that, under suitable assumptions, the quasiseparable structure is guaranteed to be numerically present in the solution, and explicit novel estimates of the numerical rank of the offdiagonal blocks are provided. Efficient solution schemes that rely on the technology of hierarchical matrices are described, and several numerical experiments confirm the applicability and efficiency of the approaches. We develop a MATLAB toolbox that allows easy replication of the experiments and a ready-to-use interface for the solvers. The performances of the different approaches are compared, and we show that the new methods described are efficient on several classes of relevant problems
Matrix-equation-based strategies for convection–diffusion equations
No full textWe are interested in the numerical solution of nonsymmetric linear systems arising from the discretization of convection–diffusion partial differential equations with separable coefficients, dominant convection and rectangular or parallelepipedal domain. Preconditioners based on the matrix equation formulation of the problem are proposed, which naturally approximate the original discretized problem. For the considered setting, we show that the explicit solution of the matrix equation can effectively replace the linear system solution. Numerical experiments with data stemming from two and three dimensional problems are reported, illustrating the potential of the proposed methodology
Low-rank-modified Galerkin Methods for the Lyapunov Equation
No full textOf all the possible projection methods for solving large-scale Lyapunov matrix equations, Galerkin
approaches remain much more popular than minimal residual ones. This is mainly due to the different nature of the
projected problems stemming from these two families of methods. While a Galerkin approach leads to the solution of a low-dimensional matrix equation per iteration, a matrix least-squares problem needs to be solved per iteration in a minimal residual setting. The significant computational cost of these least-squares problems has steered researchers towards Galerkin methods in spite of the appealing properties of minimal residual schemes. In this paper we introduce a framework that allows for modifying the Galerkin approach by low-rank, additive corrections to the projected matrix equation problem with the two-fold goal of attaining monotonic convergence rates similar to those of minimal residual schemes while maintaining essentially the same computational cost of the original Galerkin method. We analyze the well-posedness of our framework and determine possible scenarios where we expect the residual norm attained by two low-rank-modified variants to behave similarly to the one computed by a minimal residual technique. A panel of diverse numerical examples shows the behavior and potential of our new approach
A New ParaDiag Time-Parallel Time Integration Method
No full textTime -parallel time integration has received a lot of attention in the high performance computing community over the past two decades. Indeed, it has been shown that parallel -in -time techniques have the potential to remedy one of the main computational drawbacks of parallel -in -space solvers. In particular, it is well-known that for large-scale evolution problems space parallelization saturates long before all processing cores are effectively used on today's large-scale parallel computers. Among the many approaches for time -parallel time integration, ParaDiag schemes have proven to be a very effective approach. In this framework, the time stepping matrix or an approximation thereof is diagonalized by Fourier techniques, so that computations taking place at different time steps can be indeed carried out in parallel. We propose here a new ParaDiag algorithm combining the Sherman -Morrison -Woodbury formula and Krylov techniques. A panel of diverse numerical examples illustrates the potential of our new solver. In particular, we show that it performs very well compared to different ParaDiag algorithms recently proposed in the literature
A Subspace-Conjugate Gradient Method for Linear Matrix Equations
No full textThe efficient solution of large-scale multiterm linear matrix equations is a challenging task in numerical linear algebra, and it is a largely open problem. We propose a new iterative scheme for symmetric and positive definite operators, significantly advancing methods such as truncated matrix-oriented conjugate gradients (cg). The new algorithm capitalizes on the low-rank matrix format of its iterates by fully exploiting the subspace information of the factors as iterations proceed. The approach implicitly relies on orthogonality conditions imposed over much larger subspaces than in cg, unveiling insightful connections with subspace projection methods. The new method is also equipped with memory-saving strategies. In particular, we show that for a given matrix \bfitY , the action \scrL(\bfitY ) in low-rank format may not be evaluated exactly due to memory constraints. This problem is often underestimated, though it will eventually produce out-of-memory breakdowns for a sufficiently large number of terms. We propose an ad hoc randomized range-finding strategy that appears to fully resolve this shortcoming. Experimental results with typical application problems illustrate the potential of our approach over various methods developed in the recent literature
Krylov methods for low-rank commuting generalized Sylvester equations
No full textWe consider generalizations of the Sylvester matrix equation, consisting of the sum of a Sylvester operator and a linear operator pi with a particular structure. More precisely, the commutators of the matrix coefficients of the operator pi and the Sylvester operator coefficients are assumed to be matrices with low rank. We show (under certain additional conditions) low-rank approximability of this problem, that is, the solution to this matrix equation can be approximated with a low-rank matrix. Projection methods have successfully been used to solve other matrix equations with low-rank approximability. We propose a new projection method for this class of matrix equations. The choice of the subspace is a crucial ingredient for any projection method for matrix equations. Our method is based on an adaption and extension of the extended Krylov subspace method for Sylvester equations. A constructive choice of the starting vector/block is derived from the low-rank commutators. We illustrate the effectiveness of our method by solving large-scale matrix equations arising from applications in control theory and the discretization of PDEs. The advantages of our approach in comparison to other methods are also illustrated.QC 20181127</p
The Short-term Rational Lanczos Method and Applications
No full textRational Krylov subspaces have become a reference tool in dimension reduction procedures for several application problems. When data matrices are symmetric, a short-term recurrence can be used to generate an associated orthonormal basis. In the past this procedure was abandoned because it requires twice the number of linear system solves per iteration compared with the classical long-term method. We propose an implementation that allows one to obtain the rational subspace reduced matrices at lower overall computational costs than proposed in the literature by also conveniently combining the two system solves. Several applications are discussed where the short-term recurrence feature can be exploited to avoid storing the whole orthonormal basis. We illustrate the advantages of the proposed procedure with several examples
Optimality Properties of Galerkin and Petrov-Galerkin Methods for Linear Matrix Equations
No full textGalerkin and Petrov–Galerkin methods are some of the most successful solution procedures in numerical analysis. Their popularity is mainly due to the optimality properties of their approximate solution. We show that these features carry over to the (Petrov-) Galerkin methods applied for the solution of linear matrix equations. Some novel considerations about the use of Galerkin and Petrov–Galerkin schemes in the numerical treatment of general linear matrix equations are expounded and the use of constrained minimization techniques in the Petrov–Galerkin framework is proposed
- …
