Factoring Matrices into the Product of Circulant and Diagonal Matrices

详细信息    查看全文

• 作者：Marko Huhtanen ; Allan Per?m?ki
• 关键词：Circulant matrix ; Diagonal matrix ; Sparsity structure ; Matrix factoring ; Polynomial factoring ; Multiplicative Fourier compression ; 15A23 ; 65T50 ; 65F50 ; 12D05
• 刊名：Journal of Fourier Analysis and Applications
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：21
• 期：5
• 页码：1018-1033
• 全文大小：801 KB
• 参考文献：1.Bhatia, R.: Trimming, truncating and averaging of matrices. Am. Math. Mon. 107, 602-08 (2000)MathSciNet CrossRef
  2.Brualdi, R., Ryser, H.: Combinatorial Matrix Theory. Cambridge University Press, Cambridge (1991)CrossRef
  3.Benzi, M.: Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182(2), 418-77 (2002)MathSciNet CrossRef
  4.Benzi, M., Haws, J.C., T?ma, M.: Preconditioning highly indefinite and nonsymmetric matrices. SIAM J. Sci. Comput. 22(4), 1333-353 (2000)MathSciNet CrossRef
  5.Curtis, C.W., Reiner, I.: Reiner, Representation Theory of Finite Groups and Associative Algebras. AMS Chelsea Publishing, NewYork (1962)
  6.Davis, P.: Circulant Matrices. Wiley, New York (1979)
  7.Duff, I.S., Koster, J.: The design and use of algorithms for permuting large entries to the diagonal of sparse matrices. SIAM J. Matrix Anal. Appl. 20, 889-01 (1999)MathSciNet CrossRef
  8.Friedland, S.: Maximality of the monomial group. Lin. Multilin. Algebra 18, 1- (1985)MathSciNet CrossRef
  9.Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996)
  10.Huhtanen, M.: Approximating ideal diffractive optical systems. J. Math. Anal. Appl. 345, 53-2 (2008)MathSciNet CrossRef
  11.Huhtanen, M.: The product of matrix subspaces. Linear Algebra Appl. 471, 150-68 (2015)MathSciNet CrossRef
  12.Huhtanen, M., Ruotsalainen, S.: Factoring in the metaplectic group and optics. Oper. Matrices 5, 173-81 (2011)MathSciNet CrossRef
  13.Laffey, T.: Conjugacy and factorization results on matrix groups, functional analysis and operator theory. Pol. Acad. Sci. Wars. 1994, 203-21 (1992)
  14.Milne, J.S.: Algebraic Geometry. http://?www.?jmilne.?org/?math/-/span> . (2012)
  15.Müller-Quade, J., Aagedal, H., Beth, T., Schmid, M.: Algorithmic design of diffractive optical systems for information processing. Physica D 120, 196-05 (1998)CrossRef
  16.Paulsen, V.: Completely Bounded Maps and Operator Algebras. Cambridge University Press, Cambridge (2002)
  17.Rojas, J.M.: Some speed-ups and speed limits for real algebraic geometry. J. Complex. 16, 552-71 (2000)MathSciNet CrossRef
  18.Schmid, M., Steinwandt, R., Müller-Quade, J., R?tteler, M., Beth, T.: Decomposing a matrix into circulant and diagonal factors. Linear Algebra Appl. 306, 131-43 (2000)MathSciNet CrossRef
  19.Rotman, J.J.: An Introduction to the Theory of Groups. Springer, New York (1994)
  20.Taussky, O.: The characteristic polynomial and the characteristic curve of a pencil of matrices with complex entries, ?sterreich. Akad. Wiss. Math-Nat. Kl. Sitzungsber., II 195 (1986), no. 1-, pp. 175-78
  
• 作者单位：Marko Huhtanen (1)
  Allan Per?m?ki (2)
  
  1. Department of Mathematical Sciences, University of Oulu, 90570, Oulu 57, Finland
  2. Department of Mathematics and Systems Analysis, Aalto University, Box 1100, 02015, Espoo, Finland
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Fourier Analysis
  Abstract Harmonic Analysis
  Approximations and Expansions
  Partial Differential Equations
  Applications of Mathematics
  Signal,Image and Speech Processing
  
• 出版者：Birkh盲user Boston
• ISSN：1531-5851

文摘

A generic matrix \(A\in \,\mathbb {C}^{n \times n}\) is shown to be the product of circulant and diagonal matrices with the number of factors being \(2n-1\) at most. The demonstration is constructive, relying on first factoring matrix subspaces equivalent to polynomials in a permutation matrix over diagonal matrices into linear factors. For the linear factors, the sum of two scaled permutations is factored into the product of a circulant matrix and two diagonal matrices. Extending the monomial group, both low degree and sparse polynomials in a permutation matrix over diagonal matrices, together with their permutation equivalences, constitute a fundamental sparse matrix structure. Matrix analysis gets largely done polynomially, in terms of permutations only. Keywords Circulant matrix Diagonal matrix Sparsity structure Matrix factoring Polynomial factoring Multiplicative Fourier compression