## Gaussian Elimination with Pivoting is Optimal

Loading...

##### No Access Until

##### Permanent Link(s)

##### Collections

##### Other Titles

##### Authors

##### Abstract

V. Strassen discovered that two matrices of order 2 could be multiplied using 7 multiplications and 18 additions of numberss and has shown that two matrices of order n could be multiplied in less than $4 \cdot 7 n^{\log_{2}7}$ operations, an operation being defined as a multiplication, division, subtraction or addition. Also he has shown that the classical Gaussian elimination is not optimal by giving an algorithm to compute the inverse of a nonsingular matrix with certain principal submatrices nonsingular in less than $5 \cdot 64 n^{\log_{2}7}$ operations. In other words, Strassen's algorithm provides no room for pivoting. J. Bunch and J. Hopcroft have got rid of the above anomaly and have shown how to obtain the triangular factorization of a permutation of a nonsingular matrix in less than $2 \cdot 44 n^{\log_{2}7}$ operations and the inverse in less than$6 \cdot 83 n^{\log_{2}7}$ operations. In this thesis it is shown, using the results of Strassen and Bunch and Hopcroft, that Gaussian elimination with pivoting is optimal in the sense that the bound for the number of operations required to do Gaussian elimination is the least for "sufficiently large" systems of equations. Also expressions are derived for the various coefficients in the bounds for the various procedures that arise in solving linear systems of equations with the general assumption that two matrices of order u could be multiplied in p multiplications and q additions of numbers.

##### Journal / Series

##### Volume & Issue

##### Description

##### Sponsorship

##### Date Issued

1973-07

##### Publisher

Cornell University

##### Keywords

computer science; technical report

##### Location

##### Effective Date

##### Expiration Date

##### Sector

##### Employer

##### Union

##### Union Local

##### NAICS

##### Number of Workers

##### Committee Chair

##### Committee Co-Chair

##### Committee Member

##### Degree Discipline

##### Degree Name

##### Degree Level

##### Related Version

##### Related DOI

##### Related To

##### Related Part

##### Based on Related Item

##### Has Other Format(s)

##### Part of Related Item

##### Related To

##### Related Publication(s)

##### Link(s) to Related Publication(s)

##### References

##### Link(s) to Reference(s)

##### Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-176

##### Government Document

##### ISBN

##### ISMN

##### ISSN

##### Other Identifiers

##### Rights

##### Rights URI

##### Types

technical report