How to calculate the inversion of a triangular matrix 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?
 A: 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 k

The 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 k

This web-site has some nice C-code for different linear algebra algorithms: http://www.mymathlib.com
Triangular matrix inversion is here: http://www.mymathlib.com/matrices/linearsystems/triangular.html
A: 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.

