Matrix computations and polynomial root-finding with preprocessing

Solution of homogeneous linear systems of equations is a basic operation of matrix computations. The customary algorithms rely on pivoting, orthogonalization and SVD, but we employ randomized preprocessing instead. This enables us to accelerate the solution dramatically, both in terms of the estimated arithmetic cost and the observed CPU time. The approach is effective in the cases of both general and structured input matrices and we extend it and its computational advantages to the solution of nonhomogeneous linear systems of equations, matrix eigen-solving, the solution of polynomial and secular equations, and approximation of a matrix by a nearby matrix that has a smaller rank or a fixed structure (e.g., of the Toeplitz or Hankel type). Our analysis and extensive experiments show the power of the presented algorithms.     

Additive preconditioning for matrix computations

Our randomized additive preconditioners are readily available and regularly facilitate the solution of linear systems of equations and eigen-solving for a very large class of input matrices. We study the generation of such preconditioners and their impact on the rank and the condition number of a matrix. We also propose some techniques for their refinement and two alternative versions of randomized preprocessing. Our analysis and experiments show the power of our approach even where we employ weak randomization, that is generate sparse and structured preconditioners, defined by a small number of random parameters.     

Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems

A fast numerical algorithm for solving systems of linear equations with tridiagonal block Toeplitz matrices is presented. The algorithm is based on a preliminary factorization of the generating quadratic matrix polynomial associated with the Toeplitz matrix, followed by the Sherman-Morrison-Woodbury inversion formula and solution of two bidiagonal and one diagonal block Toeplitz systems. Tight estimates of the condition numbers are provided for the matrix system and the main matrix systems generated during the preliminary factorization. The emphasis is put on rigorous stability analysis to rounding errors of the Sherman-Morrison-Woodbury inversion. Numerical experiments are provided to illustrate the theory.     

ABS methods for continuous and integer linear equations and optimization

ABS methods are a large class of algorithms for solving continuous and integer linear algebraic equations, and nonlinear continuous algebraic equations, with applications to optimization. Recent work by Chinese researchers led by Zunquan Xia has extended these methods also to stochastic, fuzzy and infinite systems, extensions not considered here. The work on ABS methods began almost thirty years. It involved an international collaboration of mathematicians especially from Hungary, England, China and Iran, coordinated by the university of Bergamo. The ABS method are based on the rank reducing matrix update due to Egerváry and can be considered as the most fruitful extension of such technique. They have led to unification of classes of methods for several problems. Moreover they have produced some special algorithms with better complexity than the standard methods. For the linear integer case they have provided the most general polynomial time class of algorithms so far known; such algorithms have been extended to other integer problems, as linear inequalities and LP problems, in over a dozen papers written by Iranian mathematicians led by Nezam Mahdavi-Amiri. ABS methods can be implemented generally in a stable way, techniques existing to enhance their accuracy. Extensive numerical experiments have shown that they can outperform standard methods in several problems. Here we provide a review of their main properties, for linear systems and optimization. We also give the results of numerical experiments on some linear systems. This paper is dedicated to Professor Egerváry, developer of the rank reducing matrix update, that led to ABS methods.     

To solving problems of algebra for two-parameter matrices. IV

This paper continues the series of publications devoted to surveying and developing methods for solving the following problems for a two-parameter matrix F (λ, μ) of general form: exhausting points of the mixed regular spectrum of F (λ, μ); performing operations on polynomials in two variables (computing the GCD and LCM of a few polynomials, division of polynomials, and factorization); computing a minimal basis of the null-space of polynomial solutions of the matrix F (λ, μ) and separation of its regular kernel; inversion and pseudo in version of polynomial and rational matrices in two variables, and solution of systems of nonlinear algebraic equations in two unknowns. Most of the methods suggested are based on rank factorizations of a two-parameter polynomial matrix and on the method of hereditary pencils. Bibliography: 8 titles.     

Low rank methods for a class of generalized Lyapunov equations and related issues

In this paper, we study possible low rank solution methods for generalized Lyapunov equations arising in bilinear and stochastic control. We show that under certain assumptions one can expect a strong singular value decay in the solution matrix allowing for low rank approximations. Since the theoretical tools strongly make use of a connection to the standard linear Lyapunov equation, we can even extend the result to the $d$ -dimensional case described by a tensorized linear system of equations. We further provide some reasonable extensions of some of the most frequently used linear low rank solution techniques such as the alternating directions implicit (ADI) iteration and the Krylov-Plus-Inverted-Krylov (K-PIK) method. By means of some standard numerical examples used in the area of bilinear model order reduction, we will show the efficiency of the new methods.     

ON THE ACCURACY OF THE LEAST SQUARES AND THE TOTAL LEAST SQUARES METHODS

Consider solving an overdetermined system of linear algebraic equations by both the least squares method (LS) and the total least squares method (TLS). Extensive published computational evidence shows that when the original system is consistent. one often obtains more accurate solutions by using the TLS method rather than the LS method. These numerical observations contrast with existing analytic perturbation theories for the LS and TLS methods which show that the upper bounds for the LS solution are always smaller than the corresponding upper bounds for the TLS solutions. In this paper we derive a new upper bound for the TLS solution and indicate when the TLS method can be more accurate than the LS method.Many applied problems in signal processing lead to overdetermined systems of linear equations where the matrix and right hand side are determined by the experimental observations (usually in the form of a lime series). It often happens that as the number of columns of the matrix becomes larger, the ra     

吴消元法在Lagrange和Hamilton方程中的应用

主要借鉴吴消元法,研究带约束动力学中多项式类型Lagrange方程和Hamilton方程,提出了一种求约束的新算法．与以前算法相比,新算法无需求Hessian矩阵的秩,无需判定方程的线性相关性,从而大为减少了计算步骤,且计算更为简单．此外,计算过程中膨胀较小,且多数情形下无膨胀．利用符号计算软件,新算法可在计算机上实现．     

Solution theory for systems of bilinear equations

Bilinear systems of equations are defined, motivated and analysed for solvability. Elementary structure is mentioned and it is shown that all solutions may be obtained as rank one completions of a linear matrix polynomial derived from elementary operations. This idea is used to identify bilinear systems that are solvable for all right-hand sides and to understand solvability when the number of equations is large or small.     

Acceleration of randomized Kaczmarz method via the Johnson–Lindenstrauss Lemma

The Kaczmarz method is an algorithm for finding the solution to an overdetermined consistent system of linear equations Ax = b by iteratively projecting onto the solution spaces. The randomized version put forth by Strohmer and Vershynin yields provably exponential convergence in expectation, which for highly overdetermined systems even outperforms the conjugate gradient method. In this article we present a modified version of the randomized Kaczmarz method which at each iteration selects the optimal projection from a randomly chosen set, which in most cases significantly improves the convergence rate. We utilize a Johnson–Lindenstrauss dimension reduction technique to keep the runtime on the same order as the original randomized version, adding only extra preprocessing time. We present a series of empirical studies which demonstrate the remarkable acceleration in convergence to the solution using this modified approach.     

A projection method to solve linear systems in tensor format

In this paper, we propose a method for the numerical solution of linear systems of equations in low rank tensor format. Such systems may arise from the discretisation of PDEs in high dimensions, but our method is not limited to this type of application. We present an iterative scheme, which is based on the projection of the residual to a low dimensional subspace. The subspace is spanned by vectors in low rank tensor format which—similarly to Krylov subspace methods—stem from the subsequent (approximate) application of the given matrix to the residual. All calculations are performed in hierarchical Tucker format, which allows for applications in high dimensions. The mode size dependency is treated by a multilevel method. We present numerical examples that include high‐dimensional convection–diffusion equations.Copyright © 2012 John Wiley & Sons, Ltd.     

Operator Identities and the Solution of Linear Matrix Difference and Differential Equations

We use operator identities in order to solve linear homogeneous matrix difference and differential equations and we obtain several explicit formulas for the exponential and for the powers of a matrix as an example of our methods. Using divided differences we find solutions of some scalar initial value problems and we show how the solution of matrix equations is related to polynomial interpolation.     

Finite time stability and relative controllability of Riemann‐Liouville fractional delay differential equations

This paper firstly deals with finite time stability (FTS) of Riemann‐Liouville fractional delay differential equations via giving a series of properties of delayed matrix function of Mittag‐Leffler. We secondly study relative controllability of such type‐controlled system. With the help of the representation of solution, both Gram‐like type matrix and rank criterion are derived, which extend the corresponding results for linear systems.     

Systems of word equations,polynomials and linear algebra: A new approach

We develop a new tool, namely polynomial and linear algebraic methods, for studying systems of word equations. We illustrate its usefulness by giving essentially simpler proofs of several hard problems. At the same time we prove extensions of these results. Finally, we obtain the first nontrivial upper bounds for the fundamental problem of the maximal size of independent systems. These bounds depend quadratically on the size of the shortest equation. No methods of having such bounds have been known before.     

Inversion of polynomial and rational matrices

The inversion of polynomial and rational matrices is considered. For regular matrices, three algorithms for computing the inverse matrix in a factored form are proposed. For singular matrices, algorithms of constructing pseudoinverse matrices are considered. The algorithms of inversion of rational matrices are based on the minimal factorization which reduces the problem to the inversion of polynomial matrices. A class of special polynomial matrices is regarded whose inverse matrices are also polynomial matrices. Inversion algorithms are applied to the solution of systems with polynomial and rational matrices. Bibliography: 3 titles. Translated by V. N. Kublanovskaya. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 97–109.     

一类幂等半环上线性方程组的解法

极大-极小-加系统规划的全局优化可用于通信网络、柔性制造、对策博弈等实际系统,而幂等半环上线性方程理论在极大-极小-加系统规划的全局优化的研究中起着关键的作用.对于一类幂等半环上的非齐次线性方程组,引入列满秩矩阵与控制向量概念,并分别给出解的存在性和惟一性充分必要条件以及求解方法.     

两类循环分块矩阵及其有关算法

本文利用多项式矩阵最大右公因式，给出R-循环分块矩阵的和对称R-循环分块矩阵非奇异以及线性方程组反问题有唯一解的充要条件，进而得到它们求逆、线性方程组唯一解、线性方程组在循环分块矩阵中的反总问题求唯一解的算法。     

Some results in the theory of the vector ε-algorithm

The solution of systems of linear equations by mean of the vector ε-algorithm is investigated. The cases with a singular matrix are studied which show that, under certain assumptions on the minimal polynomial of the matrix, a solution can be obtained. Some theorems concerning the application of the ε-algorithm to vectors satisfying a matrix difference equation are proved. These results generalize results on the scalar ε-algorithm and some recent theorems on the vector ε-algorithm.     

A new error in variables model for solving positive definite linear system using orthogonal matrix decompositions

The need to estimate a positive definite solution to an overdetermined linear system of equations with multiple right hand side vectors arises in several process control contexts. The coefficient and the right hand side matrices are respectively named data and target matrices. A number of optimization methods were proposed for solving such problems, in which the data matrix is unrealistically assumed to be error free. Here, considering error in measured data and target matrices, we present an approach to solve a positive definite constrained linear system of equations based on the use of a newly defined error function. To minimize the defined error function, we derive necessary and sufficient optimality conditions and outline a direct algorithm to compute the solution. We provide a comparison of our proposed approach and two existing methods, the interior point method and a method based on quadratic programming. Two important characteristics of our proposed method as compared to the existing methods are computing the solution directly and considering error both in data and target matrices. Moreover, numerical test results show that the new approach leads to smaller standard deviations of error entries and smaller effective rank as desired by control problems. Furthermore, in a comparative study, using the Dolan-Moré performance profiles, we show the approach to be more efficient.