Browse Prior Art Database

A HIGHLY EFFICIENT ARBITRARY DETERMINANT

IP.com Disclosure Number: IPCOM000006395D
Original Publication Date: 1992-May-01
Included in the Prior Art Database: 2001-Dec-31
Document File: 4 page(s) / 206K

Publishing Venue

Motorola

Related People

Scott E. Lloyd: AUTHOR

Abstract

This publication describes a highly efficient method for computing an arbitrary determinant. Arbitrary mean- ing the determinant matrix requires no special form or symmetry to benefit from this solution.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 31% of the total text.

Page 1 of 4

0 M

MOTOROLA INC. Technical Developments Volume 15 May 1992

A HIGHLY EFFICIENT ARBITRARY DETERMINANT

by Scott E. Lloyd

  This publication describes a highly efficient method for computing an arbitrary determinant. Arbitrary mean- ing the determinant matrix requires no special form or symmetry to benefit from this solution.

  For computing a determinant of size greater than 4 X 4, various methods exist which are considered efi- cient relative to the computational complexity of the fun- damental Laplace expansion. However, these methods require division whereas the Laplace Expansion method requires only multiplication and addition-no division.

  For low-order determinants (size less than 5 X 5) the Laplace expansion is simple, and preferred over more complicated efficient methods requiring division. However, for high-order determinants (size greater than 4 X 4) many efficient methods exist which are less com- putationally intensive than the Laplacian expansion if division and multiplication are weighted equally (i.e. divi- sion and multiplication take the same amount of time to compute). Also, the assumption is traditionally made that addition is insignificant compared to multiplication and division. These might be reasonable assumptions for a mathematician to make if intending to add, multi- ply, and divide by hand not taking advantage of any kind of computing technology.

  However, known implementation technologies dic- tate that these assumptions are not necessarily correct. For most technologies, the computation time of division is greater than multiplication, which is greater than addi- tion. Any given technology has an associated relative weighting between these three fundamental computations.

  Structural implementation relates to the level of abstraction (e.g. processor, register-transfer-level, logic gates, etc.) in the structural domain of design descrip- tion. This implementation determines the relative weighting between addition, multiplication, and division. For n-bit accuracy in the digital realm, a typical general- purpose DSP takes n times as long to compute a division than a multiplication, which takes the same amount of time as an addition. However, a typical microprocessor

0 Motorola. Inc. 1992

might take four times as long to compute a division than a multiplication, which might take two to four times as long to compute than an addition. A typical logic gate implementation would take about twice as long to com- pute a multiplication than an addition. If registers are also used, multiplication could take n times as long as addition, and division about 2"+ ' times as long as addition.

  Due to the reality of structural implementation con- straints, division should be minimized relative to multi- plication and addition, if computation time is a consideration. Also, multiplication should be minimized relative to addition, which is not necessarily negligible.

  In general, but depending on structural implemen- tation-addition is no...