Department of Computational and Data Sciences
Department Seminar
Speaker : Murugesan Venkatapathi,Department of Computational & Data Sciences.
Title : The circulant decomposition of a matrix and fast multiplication of large matrices.
Date & Time : August 30, 2024, 4:00 PM
Venue : # 202, CDS Class room
ABSTRACT
The well-known singular-value decomposition of a matrix, and the eigenvalue decomposition of a non-defective square matrix, have become indispensable in engineering and sciences. Here, the matrix is a weighted sum of rank-one matrices with the corresponding singular-value or the eigenvalue as the weight. Typically, a decomposition is useful if a few significant components in the sum contain most of the required information in the matrix.
Another decomposition of a n x n matrix was proposed here at the Institute, where the matrix is a sum of ‘n’ circulant matrices (with fixed periodic relaxations on the unit circle). This decomposition is orthogonal with respect to a certain inner product of matrices and allows a simple projection for the circulant matrices. Alternately, a more efficient evaluation of all circulant components is also possible in O(n^2 . logn) operations exploiting the Fast-Fourier-Transform (FFT). Note that a circulant matrix has at most ‘n’ unique entries cyclically permuting both in its rows and columns. Relatively few dominant circulant components may be sufficient in approximating a dense matrix when it has some periodicity in its entries. For such matrices, this decomposition was used in approximating eigenvalues and sparse similarity transformations, and to precondition linear solvers.
More generally, the circulant decomposition was recently used to demonstrate iterative multiplication of two matrices in O(n^2 . logn^2) i.e. Õ(n^2) arithmetic operations, with well-bounded relative errors less than 1% unlike other restricted methods approximating matrix multiplication. Further, this decomposition may have additional gains in a quantum computation. The talk is designed to introduce this matrix decomposition to students.
ALL ARE WELCOME
