0
$\begingroup$

LU factorization with partial pivoting is carried out without access to the right hand side vector of a linear system. We have to keep track of the row interchanges carried out during the factorization process, so that we can apply the same row interchange to the right hand side vector. We do this by applying all the row interchanges carried out during the LU - factorization to the identity matrix.

This gives rise to the permutation matrix P. By definition, permutation matrices are matrices obtained by interchanging rows in the identity matrix, and it has precisely in each row and column, an entry 1. Storing the permutation matrix P, just because we would like to keep track of the row interchanges we are carrying out is a bit clumsy, and maybe unnecessary. Perhaps, performing PA = LU factorization does not require storage of an n ×n matrix P.

Can you describe a more compact way to represent the information coming from row interchanges?

$\endgroup$
0
$\begingroup$

We do not need $n\times n$ space complexity to represent a permutation. We can do so by space complexity of $n$.

For example, we can use the one line notation to represent the permutation. That is we just have to track where does the row $i$ goes to. Suppose $i$ goes to $\sigma(i)$, we just have to record

$$(\sigma(1), \ldots, \sigma(n))$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.