1,721,005 research outputs found
On the use of certain matrix algebras associated with trigonometric transforms in matrix displacement decomposition
No full textThe authors extend some recent results of Di Fiore and Zellini [Linear Algebra Appl.,
to appear], obtaining new classes of formulas for the displacement operator-based decomposition
of matrices. It is shown how an arbitrary matrix can be expressed as the sum of products of
matrices belonging to matrix algebras associated with certain versions of sine and cosine transforms.
Applications to the representation of the inverse of a Toeplitz and a Toeplitz plus Hankel matrix,
with and without symmetry, are presented. Implications on the computation of the product of these
matrices by a vector are discussed
A variation of Broyden class methods using Householder adaptive transforms
No full textIn this work we introduce and study novel Quasi Newton minimization methods based on a Hessian approximation Broyden Class-type updating scheme, where a suitable matrix Btilde_k is updated instead of the current Hessian approximation B_k. We identify conditions which imply the convergence of the algorithm and, if exact line search is chosen, its quadratic termination. By a remarkable connection between the projection operation and Krylov spaces, such conditions can be ensured using low complexity matrices Btilde_k obtained projecting B_k onto algebras of matrices diagonalized by products of two or three Householder matrices adaptively chosen step by step. Experimental tests show that the introduction of the adaptive criterion, which theoretically guarantees the convergence, considerably improves the robustness of the minimization schemes when compared with a non-adaptive choice; moreover, they show that the proposed methods could be particularly suitable to solve large scale problems where L-BFGS is not able to deliver satisfactory performance
Matrix algebras and displacement decompositions
No full textA class xi of algebras of symmetric nxn matrices, related to Toeplitz-plus-Hankel structures and including the well-known algebra H diagonalized by the Hartley transform, is investigated. The algebras of xi are then exploited in a general displacement decomposition of an arbitrary nxn matrix A. Any algebra of xi is a 1-space, i.e., it is spanned by n matrices having as first rows the vectors of the canonical basis. The notion of 1-space (which generalizes the previous notions of L1 space [Bevilacqua and Zellini, Linear and Multilinear Algebra, 25 (1989), pp.1-25] and Hessenberg algebra [Di Fiore and Zellini, Linear Algebra Appl., 229 (1995), pp.49-99]) finally leads to the identification in xi of three new (non-Hessenberg) matrix algebras close to H, which are shown to be associated with fast Hartley-type transforms. These algebras are also involved in new efficient centrosymmetric Toeplitz-plus-Hankel inversion formulas
Algebras Closed by J-Hermitianity in Displacement Formulas
No full textAbstract: We introduce the notion of J-Hermitianity of a matrix, as a generalization of Hermitianity, and, more generally, of closure by J-Hermitianity of a set of matrices. Many well known algebras, like upper and lower triangular Toeplitz, Circulants and τmatrices, as well as certain algebras that have dimension higher than the matrix order, turn out to be closed by J-Hermitianity. As an application, we generalize some theorems about displacement decompositions presented in [1, 2], by assuming the matrix algebras involved closed by J-Hermitianity. Even if such hypothesis on the structure is not necessary in the case of algebras generated by one matrix, as it has been proved in [3], our result is relevant because it could yield new low complexity displacement formulas involving not one-matrix-generated commutative algebras
Optimal rank matrix algebras preconditioners
Full text linkWhen a linear system Ax = y is solved by means of iterative methods (mainly CG and GMRES) and the convergence rate is slow, one may consider a preconditioner P and move to the preconditioned system P-1 Ax = P(-1)y. The use of such preconditioner changes the spectrum of the matrix defining the system and could result into a great acceleration of the convergence rate. The construction of optimal rank preconditioners is strongly related to the possibility of splitting A as A = P R E. where E is a small perturbation and R is of low rank (Tyrtyshnikov, 1996) [1]. In the present work we extend the black-dot algorithm for the computation of such splitting for P circulant (see Oseledets and Tyrtyshnikov, 2006 [2]), to the case where P is in A, for several known low-complexity matrix algebras A. The algorithm so obtained is particularly efficient when A is Toeplitz plus Hankel like. We finally discuss in detail the existence and the properties of the decomposition A = P+R+E when A is Toeplitz, also extending to the phi-circulant and Hartley-type cases some results previously known for P circulant
Structured matrices in unconstrained minimization methods
No full textStructured matrix algebras L and a generalized BFGS-type iterative scheme have been recently exploited to introduce low complexity quasi-Newton methods, named LQN, for solving general (nonstructured)minimization problems. In this paper we study the "inverse" LQN methods, which define inverse Hessian approximations by an inverse BFGS-type updating procedure. As the known LQN, the inverse LQN methods can be implemented with only O(n log_2 n) arithmetic operations per step and O(n) memory allocations. Moreover, they turn out to be particularly useful in the study of conditions on L which guarantee the extension of the fast BFGS local convergence properties to LQN-type algorithms
The Jordan and Frobenius pairs of the inverse
No full textGiven a matrix A ∈ Cn×n there exists a nonsingular matrix V such
that V−1AV = J, where J is a very sparse matrix with a diagonal block
structure, known as the Jordan canonical form (JCF) of A. Assume
that A is nonsingular and that V and J are given. How to obtain Vˆ
and ˆJ such that Vˆ −1A−1Vˆ = ˆJ and ˆJ is the JCF of A−1? Curiously, the
answer involves the Pascal matrix. For the Frobenius canonical form
(FCF), where blocks are companion matrices, the analogous question has a very simple answer. Jordan blocks and companions are
non-derogatory lower Hessenberg matrices. The answers to the two
questions will be obtained by solving two linear matrix equations
involving these matrices
Matrix displacement decompositions and apllications to Toeplitz linear systems
No full textUsing the approach of Bozzo, Di Fiore, and Zellini, new matrix displacement decomposition formulas are introduced. It is shown how an arbitrary square matrix A can be expressed as sums of products of Hessenberg algebra matrices and high level (block) matrices whose submatrices are Hessenberg algebra matrices and have variable sizes. In most cases these block factors are block-diagonal matrices. Then these formulas are used in sequential and parallel solution of Toeplitz systems
- …
