Search

This work is concerned with the consistency conditions for the equations in max plus algebra. The three classes of the max plus linear equations presented in the paper Shinzawa [Ultra discrete permanent and the consistency of max plus linear equations, Linear Algebra Appl. 506 (2016) 445–477] can be equivalently converted into the corresponding system of inequalities. The equivalence relation between ultra discrete permanent and maximum cycle mean is suggested. Thus, the necessary and sufficient conditions for solvability of the equations are obtained using the maximum cycle mean in this note. [ABSTRACT FROM AUTHOR]

In this paper, we present a minimum residual based gradient iterative method for solving a class of matrix equations including Sylvester matrix equations and general coupled matrix equations. The iterative method uses a negative gradient as steepest direction and seeks for an optimal step size to minimize the residual norm of next iterate. It is shown that the iterative sequence converges unconditionally to the exact solution for any initial guess and that the norm of the residual matrix and error matrix decrease monotonically. Numerical tests are presented to show the efficiency of the proposed method and confirm the theoretical results. [ABSTRACT FROM AUTHOR]

A class of perturbed Toeplitz-plus-Hankel matrices are studied in this paper. Firstly, we present two fast algorithms for computing the eigenvalues of a Toeplitz-plus-Hankel matrix which can be diagonalized by discrete cosine transform. Based on the diagonalization of the Toeplitz-plus-Hankel matrix, algorithms for fast Toeplitz-plus-Hankel matrix-vector multiplication and solving the Toeplitz-plus-Hankel system are given. Secondly, we propose two new algorithms with less computational time to solve the perturbed Toeplitz-plus-Hankel linear system. Thirdly, image encryption and decryption utilizing the proposed algorithms are shown. Finally, the effectiveness of our proposed algorithms is verified by numerical experiments. [ABSTRACT FROM AUTHOR]

We will study applications of numerical methods in Clifford algebras in ℝ 4 , in particular in the skew field of quaternions, in the algebra of coquaternions and in the other nondivision algebras in ℝ 4 . In order to gain insight into the multidimensional case, we first consider linear equations in quaternions and coquaternions. Then we will search for zeros of one-sided (simple) quaternion polynomials. Three different classes of zeros can be distinguished. In general, the quaternionic coefficients can be placed on both sides of the powers. Then there are even five different classes of zeros. All results can be extended to other noncommutative algebras in ℝ 4 . In the paper by R. Lauterbach and G. Opfer (2014), the authors constructed an exact Jacobi matrix for functions defined in noncommutative algebraic systems without the use of any partial derivative. We applied this technique to find the eigenvalues of the companion matrix as zeros of the companion polynomial by Newton's method. [ABSTRACT FROM AUTHOR]

Recently, a number of efficient iteration methods for the solution of a special class of block 3 × 3 saddle point systems have been proposed by some authors. In order to easily evaluate the strong stability of these numerical algorithms and provide a practical and reliable termination criterion, in this paper, we perform the structured backward error analysis for this type of block 3 × 3 saddle point system and present an explicit and computable formula of the normwise structured backward error. Some numerical experiments are performed to demonstrate that our results can be used to easily test the stability of running algorithms, and the new stopping criterion based on the derived structured backward error is more suitable and efficient than the commonly used residue-based one. [ABSTRACT FROM AUTHOR]

This paper aims to study the local derivations, 2-local automorphisms and local automorphisms on the super-Virasoro algebras. The primary focus is to establish that every local derivation of the super-Virasoro algebras is indeed a derivation, and to demonstrate that every local or 2-local automorphism of the super-Virasoro algebras is an automorphism. [ABSTRACT FROM AUTHOR]

In the present paper, we mainly consider the direct solution of periodic pentadiagonal Toeplitz linear systems. By exploiting the low-rank and Toeplitz structure of the coefficient matrix, we derive a new matrix decomposition of periodic pentadiagonal Toeplitz matrices. Based on this matrix decomposition form and combined with the Sherman-Morrison-Woodbury formula, we propose an efficient algorithm for numerically solving periodic pentadiagonal Toeplitz linear systems. Furthermore, we present a fast and reliable algorithm for evaluating the determinants of periodic pentadiagonal Toeplitz matrices by a certain type of matrix reordering and partitioning, and linear transformation. Numerical examples are given to demonstrate the performance and effectiveness of our algorithms. All of the experiments are performed on a computer with the aid of programs written in Matlab. [ABSTRACT FROM AUTHOR]

QR decomposition is widely used for solving the least squares problem. However, existing materials about it may be too abstract for non-mathematicians, especially STEM students, and/or require serious background in linear algebra. The paper describes theoretical background and examples of GNU Octave compatible MATLAB scripts that give relatively simple but complete explanations about how to use QR decomposition for the least squares problem solution. Only basic knowledge of linear algebra and calculus are required. Both Givens rotations and Householder reflections usage for the linear least squares problem were considered. It was shown that the algorithm based on Givens rotations is even easier to program than explicit formation of the normal equations with subsequent usage of Gaussian elimination. [ABSTRACT FROM AUTHOR]

In this paper, using the real representation method, we study the reduced biquaternion matrix equation A X = B . Taking advantage of the special structure of real representation of reduced biquaternion, we transform the problem of reduced biquaternion matrix into corresponding problem of real matrix. We propose the expressions of the special minimal norm least squares solution of the reduced biquaternion matrix equation A X = B , and the corresponding algorithms only perform real arithmetic. Numerical examples are provided to illustrate that our algorithm are efficient and easily understood. We also apply the minimal norm pure imaginary least squares reduced biquaternion solution to color image restoration. [ABSTRACT FROM AUTHOR]

In this paper, we study the quaternion matrix equation (1.1) by using the semi-tensor product of matrices. First, we propose a real vector representation of a quaternion matrix and study its properties. Then combining this real vector representation with semi-tensor product of matrices, the explicit expressions of the least squares solution, the least squares J-self-conjugate solution and the least squares anti-J-self-conjugate solution of (1.1) are proposed. We give the equivalence conditions for the compatibility of (1.1) and the expressions of the minimal norm solution with above-mentioned properties. We also propose the corresponding algorithms and give numerical experiments to verify the effectiveness of our methods. [ABSTRACT FROM AUTHOR]

In practical computations, the (preconditioned) conjugate gradient (P)CG method is the iterative method of choice for solving systems of linear algebraic equations Ax = b with a real symmetric positive definite matrix A. During the iterations, it is important to monitor the quality of the approximate solution xk so that the process could be stopped whenever xk is accurate enough. One of the most relevant quantities for monitoring the quality of xk is the squared A-norm of the error vector x − xk. This quantity cannot be easily evaluated; however, it can be estimated. Many of the existing estimation techniques are inspired by the view of CG as a procedure for approximating a certain Riemann–Stieltjes integral. The most natural technique is based on the Gauss quadrature approximation and provides a lower bound on the quantity of interest. The bound can be cheaply evaluated using terms that have to be computed anyway in the forthcoming CG iterations. If the squared A-norm of the error vector decreases rapidly, then the lower bound represents a tight estimate. In this paper, we suggest a heuristic strategy aiming to answer the question of how many forthcoming CG iterations are needed to get an estimate with the prescribed accuracy. Numerical experiments demonstrate that the suggested strategy is efficient and robust. [ABSTRACT FROM AUTHOR]

In this paper we consider linear gyroscopic mechanical systems.More precisely, we consider the perturbation theory for stable gyroscopic systems. We present new relative perturbation bounds for the eigenvalues as well as the bounds for the perturbation of the corresponding eigenspaces. Derived bounds are dependent only on system matrices of the original and perturbed systems. The quality of obtained results is illustrated in the numerical experiment. [ABSTRACT FROM AUTHOR]

The block version of GMRES (BGMRES) is most advantageous over the single right hand side (RHS) counterpart when the cost of communication is high while the cost of floating point operations is not. This is the particular case on modern graphics processing units (GPUs), while it is generally not the case on traditional central processing units (CPUs). In this paper, experiments on both GPUs and CPUs are shown that compare the performance of BGMRES against GMRES as the number of RHS increases, with a particular forcus on GPU performance. The experiments indicate that there are many cases in which BGMRES is slower than GMRES on CPUs, but faster on GPUs. Furthermore, when varying the number of RHS on the GPU, there is an optimal number of RHS where BGMRES is clearly most advantageous over GMRES. A computational model for the GPU is developed using hardware specific parameters, providing insight towards how the qualitative behavior of BGMRES changes as the number of RHS increase, and this model also helps explain the phenomena observed in the experiments. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with a class of tensor equations. Some explicit solutions to these equations are obtained. They are extensions of some results given by Lancaster. At the end of the article, these results are also employed to prove Lyapunov and Stein stability theorems for tensors. [ABSTRACT FROM AUTHOR]

In this paper we study several classes of stochastic optimization algorithms enriched with heavy ball momentum. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic dual subspace ascent. This is the first time momentum variants of several of these methods are studied. We choose to perform our analysis in a setting in which all of the above methods are equivalent: convex quadratic problems. We prove global non-asymptotic linear convergence rates for all methods and various measures of success, including primal function values, primal iterates, and dual function values. We also show that the primal iterates converge at an accelerated linear rate in a somewhat weaker sense. This is the first time a linear rate is shown for the stochastic heavy ball method (i.e., stochastic gradient descent method with momentum). Under somewhat weaker conditions, we establish a sublinear convergence rate for Cesàro averages of primal iterates. Moreover, we propose a novel concept, which we call stochastic momentum, aimed at decreasing the cost of performing the momentum step. We prove linear convergence of several stochastic methods with stochastic momentum, and show that in some sparse data regimes and for sufficiently small momentum parameters, these methods enjoy better overall complexity than methods with deterministic momentum. Finally, we perform extensive numerical testing on artificial and real datasets, including data coming from average consensus problems. [ABSTRACT FROM AUTHOR]

In this paper, some sufficient conditions of identifying the positive definiteness of homogeneous polynomial forms are proposed by identifying H -tensors. Numerical examples are given to show the feasibility and effectiveness of the methods. [ABSTRACT FROM AUTHOR]

Recently, Sugihara et al. (Numer Linear Algebra Appl 27:1-25, 2020) studied the right preconditioned MINRES method for solving symmetric singular linear systems. In this paper, we discuss the left and right preconditioned MINRES method for symmetric singular linear systems with singular preconditioners. The convergence of the preconditioned MINRES method are proved under the condition of proper splitting. Numerical results demonstrate the effectiveness of the preconditioned MINRES with singular preconditioners. [ABSTRACT FROM AUTHOR]

This paper investigates the numerical solution of huge linear algebraic systems, in which the number of rows or columns of the coefficient matrix A is greater than 100,000. Considering the idea of K-means algorithm and removing partial row vectors with small initial residuals, we propose a partitioning strategy and construct the randomized partial block Kaczmarz method. The working block of each iteration is randomly selected by using the uniform distribution, and the convergence property is also analyzed. Numerical examples illustrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Machine learning (ML) problems are often posed as highly nonlinear and nonconvex unconstrained optimization problems. Methods for solving ML problems based on stochastic gradient descent are easily scaled for very large problems but may involve fine-tuning many hyper-parameters. Quasi-Newton approaches based on the limited-memory Broyden-Fletcher-Goldfarb-Shanno (BFGS) update typically do not require manually tuning hyper-parameters but suffer from approximating a potentially indefinite Hessian with a positive-definite matrix. Hessian-free methods leverage the ability to perform Hessian-vector multiplication without needing the entire Hessian matrix, but each iteration's complexity is significantly greater than quasi-Newton methods. In this paper we propose an alternative approach for solving ML problems based on a quasi-Newton trust-region framework for solving large-scale optimization problems that allow for indefinite Hessian approximations. Numerical experiments on a standard testing data set show that with a fixed computational time budget, the proposed methods achieve better results than the traditional limited-memory BFGS and the Hessian-free methods. [ABSTRACT FROM AUTHOR]

In this paper, the authors review Dr C R Rao’s contributions to statistical foundations in economic science, and the importance of his work in advancing econometric modelling and statistical inference in celebration of his birth centenary. [ABSTRACT FROM AUTHOR]

This paper presents a greedy randomized average block sampling Gauss–Seidel (GRABGS) method for solving sparse linear least-squares problems. The GRABGS method utilizes a novel probability criterion to collect the control index set of coordinates, and minimizes the quadratic convex objective by performing multiple accurate line searches on average per iteration. The probability criterion aims to capture subvectors whose norms are relatively large. Additionly, the GRABGS method is categorized as a member of randomized block Gauss–Seidel methods, which can be employed for parallel implementations. The convergence analysis encompasses two types of extrapolation stepsizes: constant and adaptive. It is proved that the GRABGS method converges to the unique solution of the sparse linear least-squares problem when the matrix has full column rank. Numerical examples demonstrate the superiority of this method over the greedy randomized coordinate descent method and several existing state-of-the-art block Gauss–Seidel methods. [ABSTRACT FROM AUTHOR]

In this paper, we investigate structured backward errors for two kinds of generalized saddle point systems. The explicit formulas of structured backward errors are derived, which are useful for testing the stability of practical algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we give algebraic conditions for the existence of a solution and the expression for the general solution of the system of the equations a 1 x b 1 = c 1 , a 2 x b 2 = c 2 , a 3 x b 3 = c 3 , when each element belongs to a ring with a unit. As an application, we get necessary and sufficient conditions for the existence of common inner inverse of three regular elements. [ABSTRACT FROM AUTHOR]

In this paper, some solution expressions to the quaternion matrix equation X− AXF= BY are obtained. They are the further conclusions of the paper (Song et al. in Int. J. Comput. Math. 89:890–900, 2012 ). By applying of Kronecker map and complex representation of a quaternion matrix, the sufficient conditions for finding the solution have been established. At the end of the article, numerical examples show the applications of the proposed explicit solution. [ABSTRACT FROM AUTHOR]

In this paper, we give the comments on the article ‘Inversion of a Generalized Vandermonde Matrix’ by M.E.A. El Mikkawy, Int. J. Computer Math. 80 (2003), pp. 759–765. The article gives an algorithm for the elementary symmetric function's calculation which contains a severe error. In these comments, we have proposed necessary corrections of that algorithm. [ABSTRACT FROM PUBLISHER]

The equivalence of multidimensional systems is closely related to the equivalence of multivariate polynomial matrices, for which the Smith form plays an important role. In this paper we study multivariate polynomial matrices with their entries in the polynomial ring K [ z 1 , z 2 , ... , z n ] , where K is an arbitrary field. We derive some new conditions on reducing these matrices to their Smith forms. These conditions can be verified by computing the reduced Gröbner bases of the associated ideals. [ABSTRACT FROM AUTHOR]

In this paper, improved algorithms are proposed for preconditioned bi-Lanczos-type methods with residual norm minimization for the stable solution of systems of linear equations. In particular, preconditioned algorithms pertaining to the bi-conjugate gradient stabilized method (BiCGStab) and the generalized product-type method based on the BiCG (GPBiCG) have been improved. These algorithms are more stable compared to conventional alternatives. Further, a stopping criterion changeover is proposed for use with these improved algorithms. This results in higher accuracy (lower true relative error) compared to the case where no changeover is done. Numerical results confirm the improvements with respect to the preconditioned BiCGStab, the preconditioned GPBiCG, and stopping criterion changeover. These improvements could potentially be applied to other preconditioned algorithms based on bi-Lanczos-type methods. [ABSTRACT FROM AUTHOR]

Low-rank Krylov methods are one of the few options available in the literature to address the numerical solution of large-scale general linear matrix equations. These routines amount to well-known Krylov schemes that have been equipped with a couple of low-rank truncations to maintain a feasible storage demand in the overall solution procedure. However, such truncations may affect the convergence properties of the adopted Krylov method. In this paper we show how the truncation steps have to be performed in order to maintain the convergence of the Krylov routine. Several numerical experiments validate our theoretical findings. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and analyze a new LU-factorization technique for square matrices over idempotent semifields. In particular, more emphasis is put on "max-plus" algebra here but the work is extended to other idempotent semifields as well. We first determine the conditions under which a square matrix has LU factors. Next, using this technique, we propose a method for solving square linear systems of equations whose system matrices are LU-factorizable. We also give conditions for an LU-factorizable system to have solutions. This work is an extension of similar techniques over fields. Maple® procedures for this LU-factorization are also included. [ABSTRACT FROM AUTHOR]

In this paper, we reconstruct matrices from their minors, and give explicit formulas for the reconstruction of matrices of orders 2 × 3, 2 × 4, 2 ×n, 3 × 6 andm×n. We also formulate the Plücker relations, which are the conditions of the existence of a matrix related to its given minors. [ABSTRACT FROM AUTHOR]

The randomized Kaczmarz algorithm has received considerable attention recently because of its simplicity, speed, and the ability to approximately solve large-scale linear systems of equations. In this paper we propose randomized double and triple Kaczmarz algorithms to solve extended normal equations of the form A ⊤ Ax = A ⊤ b - c . The proposed algorithms avoid forming A ⊤ A explicitly and work for arbitrary A ∈ R m × n (full rank or rank-deficient, m ≥ n or m < n ). Tight upper bounds showing exponential convergence in the mean square sense of the proposed algorithms are presented and numerical experiments are given to illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

In this paper, we investigate three canonical forms of interval convex quadratic programming problems. Necessary and sufficient conditions for checking weak and strong optimality of given vector corresponding to various forms of feasible region, are established respectively. By using the concept of feasible direction, these conditions are formulated in the form of linear systems with both equations and inequalities. In addition, we provide two specific examples to illustrate the efficiency of the conditions. [ABSTRACT FROM AUTHOR]

The solution of A ⊗ x = B ⊗ y has been considered in the literature and various methods have been established. However, a solution such that the resulting product is a vector having all its components equal has not been treated to the best of our knowledge. In this paper, we study a synchronization problem A ⊗ x = B ⊗ y = α and proposed an O (m n + m k) algorithm for its solution. Where m is the number of rows of the matrices and n a n d k are the number of columns of A a n d B respectively. That is, given any Two matrices that have the same number of rows, m we introduce some algorithm that generates two column vectors x a n d y such that A ⊗ x = B ⊗ y = α , where A a n d B assumed to be P-doubly G-astic matrices having the same number of rows and α is a column vector having all its components equal. [ABSTRACT FROM AUTHOR]