 Bareiss algorithm

In mathematics, the Bareiss algorithm, named after Erwin Bareiss, is an algorithm to calculate the determinant 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 roundoff errors beyond those already present in the input.
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^{nL}) bound on the absolute value of intermediate values needed.
Calculating the determinant
To compute the determinant using the bareiss algorithm you must find the total number of elements in each row and multiply them by the total number of elements in each column.
References
 Bareiss, Erwin (1968), "Sylvester's Identity and Multistep IntegerPreserving Gaussian Elimination", Mathematics of computation 22 (102): 565–578, http://www.ams.org/journals/mcom/196822103/S00255718196802268290/S00255718196802268290.pdf.
External links
 Yap, Chee, "Linear Systems", Fundamental Problems of Algorithmic Algebra, http://cs.nyu.edu/~yap/book/alge/ftpSite/l10.ps.gz
Numerical linear algebra Key concepts Problems Hardware Software Categories: Determinants
 Numerical linear algebra
 Exchange algorithms
 Algorithm stubs
Wikimedia Foundation. 2010.
Look at other dictionaries:
Determinant — This article is about determinants in mathematics. For determinants in epidemiology, see Risk factor. In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific… … Wikipedia
Computational complexity of mathematical operations — The following tables list the running time of various algorithms for common mathematical operations. Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.[1] See big O notation for an explanation … Wikipedia
List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… … Wikipedia