Bareiss algorithm

In mathematics, the Bareiss algorithm, named after Erwin Bareiss, is an algorithm to calculate the determinant or the echelon form of a matrix with integer entries using only integer arithmetic; any divisions that are performed are guaranteed to be exact (there is no remainder). The method can also be used to compute the determinant of matrices with (approximated) real entries, avoiding the introduction of any round-off errors beyond those already present in the input.

In mathematics, the Bareiss algorithm, named after Erwin Bareiss, is an algorithm to calculate the determinant or the echelon form of a matrix with integer entries using only integer arithmetic; any divisions that are performed are guaranteed to be exact (there is no remainder). The method can also be used to compute the determinant of matrices with (approximated) real entries, avoiding the introduction of any round-off errors beyond those already present in the input. ==Overview== The definition of the determinant of a matrix involves only the operations of multiplication, addition and subtraction. Therefore the determinant of a matrix is an integer whenever all the entries are integers. However, actual computation of the determinant using the definition or Leibniz formula is impractical, as it requires O(n!) operations. Gaussian elimination has O(n 3 ) complexity, but introduces division, which results in round-off errors when implemented using floating point numbers. Round-off errors can be avoided if all the numbers are kept as integer fractions instead of floating point. But then the size of each element grows in size exponentially with the number of rows. Bareiss brings up a question of performing an integer-preserving elimination while keeping the magnitudes of the intermediate coefficients reasonably small. Two algorithms are suggested: Division-free algorithm — performs matrix reduction to triangular form without any division operation. Fraction-free algorithm — uses division to keep the intermediate entries smaller, but due to the Sylvester's Identity the transformation is still integer-preserving (the division has zero remainder). For completeness Bareiss also suggests fraction-producing multiplication-free elimination methods. ==Algorithm== The program structure of this algorithm is a simple triple-loop, as in the standard Gaussian elimination. However in this case the matrix is modified so that each entry contains the leading principal minor [ ] . Algorithm correctness is easily shown by induction on . Input: — an -square matrix assuming its leading principal minors [ ] are all non-zero. Let M 0,0 1 (Note: M 0,0 is a special variable) For from 1 to −1: For from +1 to : For from +1 to : Set M_{i,j} = \frac{M_{i,j} M_{k,k} - M_{i,k} M_{k,j}}{M_{k-1,k-1}} Set M i,k 0 Output: The matrix is modified in-place, each entry contains the leading minor [ ] , entry contains the determinant of the original . If the assumption about principal minors turns out to be false, e.g. if −1, −1 = 0 and some , −1 ≠ 0 ( = ,..., ) then we can exchange the −1-th row with the -th row and change the sign of the final answer. ==Analysis== During execution of the Bareiss algorithm, every integer that is computed is the determinant of a submatrix of the input matrix. This allows, using the Hadamard inequality, to bound the size of these integers. Otherwise, the Bareiss algorithm may be viewed as a variant of Gaussian elimination and needs roughly the same number of arithmetic operations. It follows that, for an n × n matrix of maximum (absolute) value 2 L for each entry, the Bareiss algorithm runs in O(n 3 ) elementary operations with an O(n n/2  2 nL ) bound on the absolute value of intermediate values needed. Its computational complexity is thus O(n 5 L 2  (log(n) 2  + L 2 )) when using elementary arithmetic or O(n 4 L (log(n) + L) log(log(n) + L))) by using fast multiplication. ==Usage== The Bareiss algorithm is not commonly used for integer matrices, because multi-modular arithmetic allows a complexity similar to that of the Bareiss algorithm with fast multiplication, and is much simpler to implement. On the other hand, the Bareiss algorithm may be used with entries in any integral domain equipped with an exact-division algorithm, and, in particular, for matrices of polynomials. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1321646446 under CC BY-SA 4.0; modifications have been made.