| dc.description.abstract | Matrix multiplication is commonly used in scientific computation. Given matrices A = (aij ) of size l × m and B = (bij ) of size m × n, the standard way to compute the product C := AB is computing cij = Σ^m k=1 aikbkj . In this case, lmn multiplications and ln(m − 1) additions are used. In 1969, V. Strassen found a surprising algorithm to multiply 2 × 2 matrices using 7 multiplications instead of 8 in the standard algorithm. In this way, n × n matrix multiplication can be computed using O(n^log^7 2 ) scalar multiplication operations. If n is large, the Strassen algorithm is much more efficient than the standard algorithm. After Strassen’s algorithm, numerous efforts were made to reduce the complexity for n × n matrix multiplication. By 1986, the bound was reduced to O(n^2.38) by Coppersmith and Winograd. However this is an asymptotic result rather than an implementable algorithm. The complexity has not been significantly improved for 30 years.
Matrix multiplication is a tensor and one way to measure the complexity is using its tensor rank. Any tensor can be written as finite sum of rank one tensors and the rank for a tensor is the least number of rank-one tensors needed in the sum. A theorem due to Strassen shows the tensor rank is a good measurement for the complexity. One Bini’s theorem demonstrates that the border rank of the matrix multiplication tensor M <n> is a complexity measurement for matrix multiplication. Even though the problem may sound simple, the border ranks of small matrix multiplication tensors are still unknown. Suppose one wants to compute the border rank of the tensor for the matrix multiplication of size m × 2 and 2 × 2 denoted by R(M<m,2,2>). R(M<m,2,2>) is closely related to the border rank of reduced matrix multiplication tensor TBCLRS,m, where one entry is set equal to zero. For small m like 2 and 3, there are good geometric configurations in the border rank algorithms for the tensor TBCLRS,m. My project is to understand the geometry of the good existing algorithms in the cases m = 2, 3. In the configuration of case m = 2, the limit 5-plane in the Grassmannian plane in the algorithm intersects with the Segre variety in three special lines. For the case m = 3, the intersection of the limiting 8-plane and the Segre variety consists of the union of a family of lines passing through a plane conic and a special sub-Segre variety. I also try to find analogous algorithms to the m = 2 case or disprove the existence of such algorithms. | en |
