How many divisions needed for LU Decomposition of a square matrix

967 Views Asked by At

If a general matrix is of dimensions $n \times n$, how many divisions are needed to compute the LU Decomposition of this matrix?

Can we say zero divisions are needed (it can be done with only multiplication and addition/subtraction)? Or should we say that $n-1$ divisions are needed in order to compute each multiplier?

1

There are 1 best solutions below

0
On BEST ANSWER

To get $U$, you have to eliminate $n(n-1)/2$ terms below the main diagonal. Each elimination requires computing the row multiplier, which involves division by the pivotal element.

Implementing this verbatim, one gets $n(n-1)/2$ divisions. However, as Algebraic Pavel notes, one can compute the reciprocal of the pivot first, and then the rest is multiplication. Hence, $n-1$ divisions.

The subsequent computation of $L$ involves no divisions.