1,721,046 research outputs found
On the numerical solution of a class of systems of linear matrix equations
Full text linkWe 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
Numerical solution of a class of third order tensor linear equations
Full text linkWe 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
Error estimates for iterative algorithms for minimizing regularized quadratic subproblems
Full text linkWe derive bounds for the objective errors and gradient residuals when finding approximations to the solution of common regularized quadratic optimization problems within evolving Krylov spaces. These provide upper bounds on the number of iterations required to achieve a given stated accuracy. We illustrate the quality of our bounds on given test examples
Matrix equation solving of PDEs in polygonal domains using conformal mappings
Full text linkWe explore algebraic strategies for numerically solving linear elliptic partial differential equations in polygonal domains. To discretize the polygon by means of structured meshes, we employ Schwarz-Christoffel conformal mappings, leading to a multiterm linear equation possibly including Hadamard products of some of the terms. This new algebraic formulation allows us to clearly distinguish between the role of the discretized operators and that of the domain meshing. Various algebraic strategies are discussed for the solution of the resulting matrix equation
A GMRES convergence analysis for localized invariant subspace ill-conditioning
No full textThe Generalized Minimal RESidual (gmres) method is a well-established strategy for iteratively solving a large linear system [Formula presented], where [Formula presented] is a nonsymmetric and nonsingular coefficient matrix, and [Formula presented]. In the analysis of its convergence for A diagonalizable, a much used upper bound for the relative residual norm involves a min-max polynomial problem over the set of eigenvalues of A, magnified by the condition number of the eigenvector matrix of A. This latter factor may cause a huge overestimation of the residual norm, making the bound nondescriptive in practice. We show that when a large condition number is caused by the almost linear dependence of a few of the eigenvectors, a more descriptive analysis of the method's behavior can be performed, irrespective of the location of the corresponding eigenvalues. The new analysis aims at capturing how the gmres polynomial deals with the ill-conditioning; as a by-product, a new upper bound for the gmres residual norm is obtained. A variety of numerical experiments illustrate our findings
Multigrid Preconditioning for Discontinuous Galerkin Discretizations of an Elliptic Optimal Control Problem with a Convection-Dominated State Equation
No full textWe consider discontinuous Galerkin methods for an elliptic distributed optimal control problem constrained by a convection-dominated problem. We prove global optimal convergence rates using an inf-sup condition, with the diffusion parameter epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}\end{document} and regularization parameter beta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}\end{document} explicitly tracked. We then propose a multilevel preconditioner based on downwind ordering to solve the discretized system. The preconditioner only requires two approximate solves of single convection-dominated equations using multigrid methods. Moreover, for the strongly convection-dominated case, only two sweeps of block Gauss-Seidel iterations are needed. We also derive a simple bound indicating the role played by the multigrid preconditioner. Numerical results are shown to support our findings
The Sherman–Morrison–Woodbury formula for generalized linear matrix equations and applications
Full text linkWe discuss the use of a matrix-oriented approach for numerically solving the dense matrix equation AX + XAT + M1XN1 + ... + MlXNl = F, with l ≥ 1, and Mi, Ni, i = 1, ..., l of low rank. The approach relies on the Sherman–Morrison–Woodbury formula formally defined in the vectorized form of the problem, but applied in the matrix setting. This allows one to solve medium size dense problems with computational costs and memory requirements dramatically lower than with a Kronecker formulation. Application problems leading to medium size equations of this form are illustrated and the performance of the matrix-oriented method is reported. The application of the procedure as the core step in the solution of the large-scale problem is also shown. In addition, a new explicit method for linear tensor equations is proposed, that uses the discussed matrix equation procedure as a key building block
Functions of rational Krylov space matrices and their decay properties
Full text linkRational Krylov subspaces have become a fundamental ingredient in numerical linear algebra methods associated with reduction strategies. Nonetheless, many structural properties of the reduced matrices in these subspaces are not fully understood. We advance in this analysis by deriving bounds on the entries of rational Krylov reduced matrices and of their functions, that ensure an a-priori decay of their entries as we move away from the main diagonal. As opposed to other decay pattern results in the literature, these properties hold in spite of the lack of any banded structure in the considered matrices. Numerical experiments illustrate the quality of our results
ANALYSIS OF THE TRUNCATED CONJUGATE GRADIENT METHOD FOR LINEAR MATRIX EQUATIONS
Full text linkThe matrix-oriented version of the conjugate gradient (CG) method can be used to approximate the solution to certain linear matrix equations. To limit memory consumption, low-rank reduction of the factored iterates is often employed, possibly leading to disruption of the regular convergence behavior. We analyze the properties of the method in the matrix regime and identify the quantities that are responsible for early termination, usually stagnation, when truncation is in effect. Moreover, we illustrate relations between CG and a projection technique directly applied to the same matrix equation
Order reduction methods for solving large-scale differential matrix riccati equations
Full text linkWe consider the numerical solution of large-scale symmetric differential matrix Riccati equations. Under certain hypotheses on the data, reduced order methods have recently arisen as a promising class of solution strategies by forming low-rank approximations to the sought after solution at selected timesteps. We show that great computational and memory savings are obtained by a reduction process onto rational Krylov subspaces as opposed to current approaches. By specifically addressing the solution of the reduced differential equation and reliable stopping criteria, we are able to obtain accurate final approximations at low memory and computational requirements. This is obtained by employing a two-phase strategy that separately enhances the accuracy of the algebraic approximation and the time integration. The new method allows us to numerically solve much larger problems than in the current literature. Numerical experiments on benchmark problems illustrate the effectiveness of the procedure with respect to existing solvers
- …
