Fast rectangular matrix multiplication and QR decomposition

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

In the last twenty-five years there has been much research into "fast" matrix multiplication methods: ones that have an asymptotically smaller operation count than conventional multiplication. Most fast methods are derived for square matrices, but they can be applied to rectangular matrices by a blocking technique. We obtain an expression for the order of the operation count for this blocked multiplication of rectangular matrices. We derive an exact operation count for Strassen's method with rectangular matrices and determine the recursion threshold that minimizes the operation count. We also show that when Strassen's method is used to multiply rectangular matrices it is more efficient to use the method on the whole product than to apply the method to square submatrices. Fast multiplication methods can be exploited in calculating a QR decomposition of an m × n matrix. We show that the operation count can be reduced from O(mn2) to O(mn1+( 1 (4-α))) by using a fast multiplication method with exponent α in conjunction with Bischof and Van Loan's WY representation of a product of Householder transformations.

Original languageEnglish
Pages (from-to)69-81
Number of pages13
JournalLinear Algebra and its Applications
Volume221
DOIs
Publication statusPublished - 31 May 1995

Keywords

  • matrix multiplication methods
  • rectangular matrices
  • blocking technique

Fingerprint

Dive into the research topics of 'Fast rectangular matrix multiplication and QR decomposition'. Together they form a unique fingerprint.

Cite this