Bareiss algorithm

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

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(n n 2nL) 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.


External links

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

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.