Now I want to write a piece of code to calculate the inversion of a triangular matrix which do it in parallel.
I know that the equation of the triangular matrix's inversion is like this:
But I want my program to calculate this parallel.In this way I can't calculate this in parallel because in each computer I can't get the data in the red circle in this picture.
Can anybody tell me is there other ways to calculate the inversion of triangular matrix?
$\endgroup$ 22 Answers
$\begingroup$The following book gives algorithms for inverting a lower triangular matrix: G. W. Stewart: Matrix Algorithms Volume I:Basic Decompositions
On page 94, two algorithms are stated.
Let L be a nonsingular lower triangular matrix of order n. The following
algorithm computes the inverse X of L.
1. for k = 1 to n
2. X[k,k] = l/L[k,k]
3. for i = k+1 to n
4. X[i,k] = -L[i, k:i-1]*X[k:i-1,k]/L[i,i]
5. end for i
6. end for kThe second one is an in-place version:
The algorithm can be modified to overwrite L with its inverse
by replacing all references to X with references to L ...
1. for k = 1 to n
2. L[k,k] = 1/L[k,k]
3. for i = k+1 to n
4. L[i, k] = -L[i, k:i-1]*L[k:i-1, k]/L[k, k]
5. end for i
6. end for kThis web-site has some nice C-code for different linear algebra algorithms:
Triangular matrix inversion is here:
$\endgroup$ 2 $\begingroup$One way to parallelize at least part of the computation is to partition the $n\times n$ invertible lower triangular matrix $L$ into blocks: $$\begin{pmatrix}L_1 & 0 \\ C & L_2\end{pmatrix}^{-1} = \begin{pmatrix}L_1^{-1} & 0 \\ -L_2^{-1}C\,L_1^{-1} & L_2^{-1}\end{pmatrix}$$ Here the $L_i$ are $n_i\times n_i$ invertible lower triangular matrices with $n_1+n_2=n$, and $C$ is a rectangular $n_2\times n_1$ matrix.
Steps:
- If $n$ is smaller than some suitable predefined value, or if all processors are busy, use the sequential algorithm.
- Set $n_1,n_2>0$ such that $n_1\approx n_2$ and $n_1+n_2=n$. For example, $n_1=\lfloor\frac{n}{2}\rfloor$ or the power of $2$ nearest to $n/2$, and $n_2=n-n_1$.
- Recursively find $L_1^{-1}$ and $L_2^{-1}$. This can be done in parallel.
- When both $L_i^{-1}$ have been computed, compute the off-diagonal-block $-L_2^{-1}C\,L_1^{-1}$. This amounts to two matrix multiplications and may be parallelizable to some degree.
Further optimization ideas:
- If the computation of $L_1^{-1}$ finishes before that of $L_2^{-1}$, begin computing $C_1=-C\,L_1^{-1}$. Computation of elements of $C_1$ can be parallelized. When $L_2^{-1}$ is available, only $L_2^{-1}C_1$ remains to be computed. Computation of its elements can be parallelized.
- Likewise, if the computation of $L_2^{-1}$ finishes before that of $L_1^{-1}$, begin computing $C_2=-L_2^{-1}C$. Computation of elements of $C_2$ can be parallelized. When $L_1^{-1}$ is available, only $C_2 L_1^{-1}$ remains to be computed. Computation of its elements can be parallelized.
