Browse Prior Art Database

Inverse of a Triangular Matrix Efficient Determination of the Boolean

IP.com Disclosure Number: IPCOM000056332D
Original Publication Date: 1980-Nov-01
Included in the Prior Art Database: 2005-Feb-14

Publishing Venue

IBM

Related People

Authors:
Gustavson, FG [+details]

Abstract

In the preceding article an algorithm for finding the transitive closure of a sparse matrix was given. One step in this algorithm was to find the Boolean inverse of a lower triangular matrix. The worst case complexity of this method is O(n/3/) if standard multiplication is used or O(n/2.8/) if the "fast methods" of Pan and Strassen are used.