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 any round-off errors beyond those already present in the input.

Analysis

During the execution of 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 2L for each entry, the Bareiss algorithm runs in O(n3) elementary operations with an O(nn/2 2nL) bound on the absolute value of intermediate values needed. Its computational complexity is thus O(n5L2 (log(n)2 + L2)) when using elementary arithmetic or O(n4L (log(n) + L) log(log(n) + L))) by using fast multiplication.

History

The general Bareiss algorithm is distinct from the Bareiss algorithm for Toeplitz matrices.

In some Spanish-speaking countries, this algorithm is also known as Bareiss-Montante, because of René Mario Montante Pardo, a professor of the Universidad Autónoma de Nuevo León, Mexico, who popularized the method among his students.

gollark: You can directly boot the kernel as an EFI binary.
gollark: On EFI systems, you do not strictly need GRUB.
gollark: https://knightos.org/, not that this "counts", being a weird OS for certain graphing calculators?
gollark: DOS?
gollark: Microcontroller-type devices will do way better.

References
  • Bareiss, Erwin H. (1968), "Sylvester's Identity and multistep integer-preserving Gaussian elimination" (PDF), Mathematics of Computation, 22 (103): 565–578, doi:10.2307/2004533, JSTOR 2004533.
  • Bareiss, Erwin H. (1966), MULTISTEP INTEGER-PRESERVING GAUSSIAN ELIMINATION (PDF). (Contains a clearer picture of the operations sequence)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.