1,721,130 research outputs found
Truncated LSQR for matrix least squares problems
No full textWe are interested in the numerical solution of the matrix least squares problem (Formula presented.) with A and C full column rank, B and D full row rank, F an n×n matrix of low rank, and ‖·‖F the Frobenius norm. We derive a matrix-oriented implementation of LSQR, and devise an implementation of the truncation step that exploits the properties of the method. Experimental comparisons with the Conjugate Gradient method applied to the normal matrix equation and with a (new) sketched implementation of matrix LSQR illustrate the competitiveness of the proposed algorithm. We also explore the applicability of our method in the context of Kronecker-based Dictionary Learning, and devise a representation of the data that seems to be promising for classification purposes
On some structural properties of generalized Lyapunov eigenproblems and application to operator preconditioning
Full text linkWe are interested in generalized matrix eigenvalue problems of the type AX+ XA= λHXH and AX+ XA= λ(HX+ XH) with A and H both symmetric and positive definite, and in their tensor counterparts. We collect several structural properties, some of which are known, together with some new spectral results. We also analyze in detail the case where the second problem stems from the discretization of linear elliptic partial differential equations by finite differences. In particular, we derive spectral properties that can be used in the numerical solution of the resulting algebraic linear system
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
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
Numerical methods for large-scale Lyapunov equations with symmetric banded data
Full text link<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>
Approximating the leading singular triplets of a large matrix function
No full textGiven a large square matrix A and a sufficiently regular function f so that f(A) is well defined, we are interested in the approximation of the leading singular values and corresponding left and right singular vectors of f(A), and in particular in the approximation of ‖f(A)‖, where ‖⋅‖ is the matrix norm induced by the Euclidean vector norm. Since neither f(A) nor f(A)v can be computed exactly, we introduce a new inexact Golub–Kahan–Lanczos bidiagonalization procedure, where the inexactness is related to the inaccuracy of the operations f(A)v, f(A)⁎v. Particular outer and inner stopping criteria are devised so as to cope with the lack of a true residual. Numerical experiments with the new algorithm on typical application problems are reported
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
Approximation of functions of large matrices with Kronecker structure
No full textWe consider the numerical approximation of f(A) b where b∈ RNand A is the sum of Kronecker products, that is A= M2⊗ I+ I⊗ M1∈ RN×N. Here f is a regular function such that f(A) is well defined. We derive a computational strategy that significantly lowers the memory requirements and computational efforts of the standard approximations, with special emphasis on the exponential and on completely monotonic functions, for which the new procedure becomes particularly advantageous. Our findings are illustrated by numerical experiments with typical functions used in applications
Stability and Accuracy of Inexact Interior Point Methods for Convex Quadratic Programming
No full textWe consider primalâdual interior point methods where the linear system arising at each iteration is formulated in the reduced (augmented) form and solved approximately. Focusing on the iterates close to a solution, we analyze the accuracy of the so-called inexact step, i.e., the step that solves the unreduced system, when combining the effects of both different levels of accuracy in the inexact computation and different processes for retrieving the step after block elimination. Our analysis is general and includes as special cases sources of inexactness due either to roundoff and computational errors or to the iterative solution of the augmented system using typical procedures. In the roundoff case, we recover and extend some known results
- …
