Plethysm and fast matrix multiplication

Motivated by the symmetric version of matrix multiplication we study the plethysm $S^k({\mathfrak{sl}}_n)$ of the adjoint representation ${\mathfrak{sl}}_n$ of the Lie group $S{L}_n$. In particular, we describe the decomposition of this representation into irreducible components for $k=3$, and find highest-weight vectors for all irreducible components. Relations to fast matrix multiplication, in particular the Coppersmith–Winograd tensor, are presented.     

Fast rectangular matrix multiplication and some applications

We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary di- mensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results:(i) we decrease from O(n~2 n~(1 o)(1)logq)to O(n~(1.9998) n~(1 o(1))logq)the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic(NC)parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n×n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii)we decrease from O(m~(1.575)n)to O(m~(1.5356)n)the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.     

Error-free matrix symmetrizers and equivalent symmetric matrices

A symmetrizer of the matrix A is a symmetric solution X that satisfies the matrix equation XA=AX. An exact matrix symmetrizer is computed by obtaining a general algorithm and superimposing a modified multiple modulus residue arithmetic on this algorithm. A procedure based on computing a symmetrizer to obtain a symmetric matrix, called here an equivalent symmetric matrix, whose eigenvalues are the same as those of a given real nonsymmetric matrix is presented.Supported by CSIR.     

On the fast matrix multiplication in the boundary element method by panel clustering

Summary The boundary element method (BEM) leads to a system of linear equations with a full matrix, while FEM yields sparse matrices. This fact seems to require much computational work for the definition of the matrix, for the solution of the system, and, in particular, for the matrix-vector multiplication, which always occurs as an elementary. In this paper a method for the approximate matrix-vector multiplication is described which requires much less arithmetical work. In addition, the storage requirements are strongly reduced.This paper reports results of a research project supported by the DFG (Schwerpunktprogramm Finite Approximationen in der Strömungsmechanik     

Fast multiplication of a recursive block Toeplitz matrix by a vector and its application

We present an algorithm for multiplying an N × N recursive block Toeplitz matrix by a vector with cost O (N log N). Its application to optimal surface interpolation is discussed.     

The stochastic ordering of mean-preserving transformations and its applications

The stochastic variability measures the degree of uncertainty for random demand and/or price in various operations problems. Its ordering property under mean-preserving transformation allows us to study the impact of demand/price uncertainty on the optimal decisions and the associated objective values. Based on Chebyshev’s algebraic inequality, we provide a general framework for stochastic variability ordering under any mean-preserving transformation that can be parameterized by a single scalar, and apply it to a broad class of specific transformations, including the widely used mean-preserving affine transformation, truncation, and capping. The application to mean-preserving affine transformation rectifies an incorrect proof of an important result in the inventory literature, which has gone unnoticed for more than two decades. The application to mean-preserving truncation addresses inventory strategies in decentralized supply chains, and the application to mean-preserving capping sheds light on using option contracts for procurement risk management.     

A generalization of the fast LUP matrix decomposition algorithm and applications

We show that any m × n matrix A, over any field, can be written as a product, LSP, of three matrices, where L is a lower triangular matrix with l's on the main diagonal, S is an m × n matrix which reduces to an upper triangular matrix with nonzero diagonal elements when the zero rows are deleted, and P is an n × n permutation matrix. Moreover, L, S, and P can be found in O(m^α?1n) time, where the complexity of matrix multiplication is O(m^α). We use the LSP decomposition to construct fast algorithms for some important matrix problems. In particular, we develop O(m^α?1n) algorithms for the following problems, where A is any m × n matrix: (1) Determine if the system of equations $\text{A}\text{x}\text{=}\text{b}$ (where $\text{b}$ is a column vector) has a solution, and if so, find one such solution. (2) Find a generalized inverse, $\text{A}{}^1$, of A (i.e., $\text{AA}{}^1\text{A = A}$). (3) Find simultaneously a maximal independent set of rows and a maximal independent set of columns of A.     

Matrix multiplication and transformations: an APOS approach

This study presents a contribution to research in undergraduate teaching and learning of linear algebra, in particular, the learning of matrix multiplication. A didactical experience consisting on a modeling situation and a didactical sequence to guide students’ work on the situation were designed and tested using APOS theory. We show results of research on students’ activity and learning while using the sequence and through analysis of student’s work and assessment questions. The didactic sequence proved to have potential to foster students’ learning of function, matrix transformations and matrix multiplication. A detailed analysis of those constructions that seem to be essential for students understanding of this topic including linear transformations is presented. These results are contributions of this study to the literature.     

A system of matrix equations and its applications

We derive the solvability conditions and an expression of the general solution to the system of matrix equations A 1X=C1 , A2Y=C2 , YB2=D2 , Y=Y*, A3Z=C3 , ZB3=D3 , Z=Z*, B4X+(B4X)+C4YC4*+D4ZD4*=A4 . Moreover, we investigate the maximal and minimal ranks and inertias of Y and Z in the above system of matrix equations. As a special case of the results, we solve the problem proposed in Farid, Moslehian, Wang and Wu’s recent paper (Farid F O, Moslehian M S, Wang Q W, et al. On the Hermitian solutions to a system of adjointable operator equations. Linear Algebra Appl, 2012, 437: 1854-1891).     

Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity

Summary The number of multiplications required for matrix multiplication, for the triangular decomposition of a matrix with partial pivoting, and for the Cholesky decomposition of a positive definite symmetric matrix, can be roughly halved if Winograd's identity is used to compute the inner products involved. Floating-point error bounds for these algorithms are shown to be comparable to those for the normal methods provided that care is taken with scaling.     

向量交换矩阵一种新的定义及应用

利用单位矩阵和基本向量给出了向量交换矩阵的一种较以往表述简单的新的定义.基于新的定义证明了向量交换矩阵的性质.给出了新定义与原有定义的等价性的证明.最后给出了矩阵克罗内克积奇异值的一个新的结论.     

Bernstein operational matrix of fractional derivatives and its applications

In this paper, Bernstein operational matrix of fractional derivative of order α in the Caputo sense is derived. We also apply this matrix to the collocation method for solving multi-order fractional differential equations. The numerical results obtained by the present method compares favorably with those obtained by various collocation methods earlier in the literature.     

矩阵代数上的局部合同变换和局部相似变换

令F表示任意域,Mn（F）表示由F上所有n×n矩阵形成的结合代数.本文的目的是研究Mn（F）上具有如下性质的两类线性映射,其中一类线性映射在Mn（F）上每一点的取值与Mn（F）的某个合同变换在该点的取值相同,另一类线性映射在Mn（F）上每一点的取值与Mn（F）的某个相似变换在该点的取值相同,随着Mn（F）上的点不同,这些合同变换和相似变换可能也不同.利用矩阵的秩、幂等阵以及幂零阵的性质,通过矩阵计算的方法证明了第一类线性映射或者是合同变换或者是合同变换与转置变换的复合,第二类线性映射或者是相似变换或者是相似变换与转置变换的复合.由这个结果可知存在真正意义上的局部合同变换和局部相似变换,从而丰富了局部映射理论的研究。     

One simple result concerning imprimitivity relations of monoids of transformations and its applications

A subsetX of an algebraA is called conditional if every congruence relation onA is uniquely determined by its congruence classes containing elements ofX. In terms of transformation monoids, it is found in which case one can be sure that a given subsetX is conditional. Some applications of this results to semigroups and lattices are demonstrated. These applications lead to known results as well as to new ones. Particularly, some sufficient conditions are obtained for semigroups and lattices to be harmonic.