Блог пользователя bvd

How to quickly calculate the determinant of a matrix?
Автор bvd, история, 8 лет назад, По-английски

This is how I normally calculate the determinant of a matrix.

However, the complexity of this algorithm is O(n!).

How to calculate it in polynomial time?

P.S: Why I need to calculate the determinant of a matrix in polynomial time?

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Your second link is one click away from an efficient algorithm, which is Gaussian elimination. See the bottom of determinant's properties.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Gaussian elimination.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Please keep in mind that Gaussian is numerically unstable in general case. It is not a problem in Laplacian matrix, as it is diagonally dominant.

→ Ответить