On Fast Matrix Inversion by Fast Matrix Multiplication

Research output: Other contribution

Abstract

Volker Strassen first suggested an algorithm to multiply matrices with worst case running time less than the conventional O(n^3) operations in 1969. He also presented a recursive algorithm with which to invert matrices, and calculate determinants using matrix multiplication. James R. Bunch & John E. Hopcroft improved upon this in 1974 by providing modifications to the inversion algorithm in the case where principal submatrices were singular, amongst other improvements. We cover the case of multivariate polynomial matrix inversion, where it is noted that conventional methods that assume a field will experience major setbacks. Initially, there existed a presentation of a fraction free formulation of inversion via matrix multiplication along with motivations in [TDS17], however analysis of this presentation was rudimentary. We hence provide a discussion of the true complexities of this fraction free method arising from matrix multiplication, and arrive at its limitations.
Original languageEnglish
Media of outputarxiv.org
Publication statusPublished - 3 Jan 2019

Keywords

  • Matrix Inversion
  • Symbolic Computation

Cite this

On Fast Matrix Inversion by Fast Matrix Multiplication. / Tonks, Zak.

2019, .

Research output: Other contribution

@misc{2c944877a69b441992d4c1aa926f49b8,
title = "On Fast Matrix Inversion by Fast Matrix Multiplication",
abstract = "Volker Strassen first suggested an algorithm to multiply matrices with worst case running time less than the conventional O(n^3) operations in 1969. He also presented a recursive algorithm with which to invert matrices, and calculate determinants using matrix multiplication. James R. Bunch & John E. Hopcroft improved upon this in 1974 by providing modifications to the inversion algorithm in the case where principal submatrices were singular, amongst other improvements. We cover the case of multivariate polynomial matrix inversion, where it is noted that conventional methods that assume a field will experience major setbacks. Initially, there existed a presentation of a fraction free formulation of inversion via matrix multiplication along with motivations in [TDS17], however analysis of this presentation was rudimentary. We hence provide a discussion of the true complexities of this fraction free method arising from matrix multiplication, and arrive at its limitations.",
keywords = "Matrix Inversion, Symbolic Computation",
author = "Zak Tonks",
year = "2019",
month = "1",
day = "3",
language = "English",
type = "Other",

}

TY - GEN

T1 - On Fast Matrix Inversion by Fast Matrix Multiplication

AU - Tonks, Zak

PY - 2019/1/3

Y1 - 2019/1/3

N2 - Volker Strassen first suggested an algorithm to multiply matrices with worst case running time less than the conventional O(n^3) operations in 1969. He also presented a recursive algorithm with which to invert matrices, and calculate determinants using matrix multiplication. James R. Bunch & John E. Hopcroft improved upon this in 1974 by providing modifications to the inversion algorithm in the case where principal submatrices were singular, amongst other improvements. We cover the case of multivariate polynomial matrix inversion, where it is noted that conventional methods that assume a field will experience major setbacks. Initially, there existed a presentation of a fraction free formulation of inversion via matrix multiplication along with motivations in [TDS17], however analysis of this presentation was rudimentary. We hence provide a discussion of the true complexities of this fraction free method arising from matrix multiplication, and arrive at its limitations.

AB - Volker Strassen first suggested an algorithm to multiply matrices with worst case running time less than the conventional O(n^3) operations in 1969. He also presented a recursive algorithm with which to invert matrices, and calculate determinants using matrix multiplication. James R. Bunch & John E. Hopcroft improved upon this in 1974 by providing modifications to the inversion algorithm in the case where principal submatrices were singular, amongst other improvements. We cover the case of multivariate polynomial matrix inversion, where it is noted that conventional methods that assume a field will experience major setbacks. Initially, there existed a presentation of a fraction free formulation of inversion via matrix multiplication along with motivations in [TDS17], however analysis of this presentation was rudimentary. We hence provide a discussion of the true complexities of this fraction free method arising from matrix multiplication, and arrive at its limitations.

KW - Matrix Inversion

KW - Symbolic Computation

M3 - Other contribution

ER -