Simple block factorization?

58 Views Asked by At

In the two substructures case for the finite element tearing and interconnecting method (FETI) from "Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations" (pp 104, Smith 1996), the finite element stiffness matrix $A$ can be represented by representing the interior indices $I$ and boundary indices $B$ as shown below:

$$ A = \begin{bmatrix} A_{II}^{(1)} & 0 & A_{IB}^{(1)} \\ 0 & A_{II}^{(2)} & A_{IB}^{(2)} \\ A_{BI}^{(1)} & A_{BI}^{(2)} & A_{BB}^{(1)} + A_{BB}^{(2)} \end{bmatrix}. \tag{1} $$

But "An Introduction to Domain Decomposition Methods: Algorithms, Theory, and Parallel Implementation" (pp 132, Dolean 2015) states "a simple computation shows that we have a block factorization" as below:

$$ \begin{bmatrix} I & 0 & 0 \\ 0 & I & 0 \\ A_{BI}^{(1)}A_{II}^{(1)^{-1}} & A_{BI}^{(2)}A_{II}^{(2)^{-1}} & I \end{bmatrix} \begin{bmatrix} A_{II}^{(1)} & 0 & 0 \\ 0 & A_{II}^{(2)} & 0 \\ 0 & 0 & S^{(1)} + S^{(2)} \end{bmatrix} \begin{bmatrix} I & 0 & A_{II}^{(1)^{-1}}A_{IB}^{(1)} \\ 0 & I & A_{II}^{(2)^{-1}}A_{IB}^{(2)} \\ 0 & 0 & I \end{bmatrix}. \tag{2} $$

How can I show that this block factorization (2) follows from (1)? And why would you perform this block factorization in the first place? Note that ${S^{(i)} = A_{BB}^{(i)} - A_{BI}^{(i)}A_{II}^{(i)^{-1}} A_{IB}^{(i)}}$ and that $I$ is the identity matrix if standing alone.

Edit:

Given (2), it's easy to see that for example, the 3rd row and 1st column element of $A$ follows easily from the corresponding matrix multiplication, $$ A_{31} = I(A_{BI}^{(1)}A_{II}^{(1)^{-1}}A_{II}^{(1)} + A_{BI}^{(2)}A_{II}^{(2)^{-1}} 0 + I 0) = A_{BI}^{(1)}, $$

but without seeing (2), I wouldn't necessarily make this observation immediately. So if you weren't given (2), how would you approach the factorization?

1

There are 1 best solutions below

0
On BEST ANSWER

You could obtain a factorization like this by using "block-row" operations. Begin with $$ A = \begin{bmatrix} A_{II}^{(1)} & 0 & A_{IB}^{(1)} \\ 0 & A_{II}^{(2)} & A_{IB}^{(2)} \\ A_{BI}^{(1)} & A_{BI}^{(2)} & A_{BB}^{(1)} + A_{BB}^{(2)} \end{bmatrix}. $$ If we multiply the first row by $A_{BI}^{(1)}[A_{II}^{(1)}]^{-1}$ (from the left), then the resulting first entry will match the $3,1$ block entry. Thus, the block-row operation $R_3 = R_3 - A_{BI}^{(1)}[A_{II}^{(1)}]^{-1}R_1$ will "zero out" the $3,1$ entry. Writing this out in matrix form, we have $$ \overbrace{\begin{bmatrix} I & 0 & 0\\ 0 & I & 0\\ -A_{BI}^{(1)}[A_{II}^{(1)}]^{-1} & 0 & I \end{bmatrix}}^{E_1} \begin{bmatrix} A_{II}^{(1)} & 0 & A_{IB}^{(1)} \\ 0 & A_{II}^{(2)} & A_{IB}^{(2)} \\ A_{BI}^{(1)} & A_{BI}^{(2)} & A_{BB}^{(1)} + A_{BB}^{(2)} \end{bmatrix} = \\ \begin{bmatrix} A_{II}^{(1)} & 0 & A_{IB}^{(1)} \\ 0 & A_{II}^{(2)} & A_{IB}^{(2)} \\ 0 & A_{BI}^{(2)} & A_{BB}^{(1)} + A_{BB}^{(2)} - A_{BI}^{(1)}[A_{II}^{(1)}]^{-1}A_{IB}^{(1)} \end{bmatrix} = \\ \begin{bmatrix} A_{II}^{(1)} & 0 & A_{IB}^{(1)} \\ 0 & A_{II}^{(2)} & A_{IB}^{(2)} \\ 0 & A_{BI}^{(2)} & S^{(1)} + A_{BB}^{(2)} \end{bmatrix}. $$ You can think of the $E_1$ as being analogous to an elementary matrix. Notably, the inverse of the "block elementary matrix" $E_1$ will be the block elementary matrix of the inverse operation, namely the matrix corresponding to $R_3 = R_3 - A_{BI}^{(1)}[A_{II}^{(1)}]^{-1}R_1$.

From there, you can find a block elementary matrix $E_2$ such that $$ E_2 \begin{bmatrix} A_{II}^{(1)} & 0 & A_{IB}^{(1)} \\ 0 & A_{II}^{(2)} & A_{IB}^{(2)} \\ 0 & A_{BI}^{(2)} & S^{(1)} + A_{BB}^{(2)} \end{bmatrix} = \begin{bmatrix} A_{II}^{(1)} & 0 & A_{IB}^{(1)} \\ 0 & A_{II}^{(2)} & A_{IB}^{(2)} \\ 0 & 0 & S^{(1)} + S^{(2)} \end{bmatrix} $$ From there, you could proceed by using block elementary matrices corresponding to row-multiplications in order to get $I$'s on the diagonal, but the punchline is that $$ \begin{bmatrix} A_{II}^{(1)} & 0 & 0 \\ 0 & A_{II}^{(2)} & 0 \\ 0 & 0 & S^{(1)} + S^{(2)} \end{bmatrix}^{-1} \begin{bmatrix} A_{II}^{(1)} & 0 & A_{IB}^{(1)} \\ 0 & A_{II}^{(2)} & A_{IB}^{(2)} \\ 0 & 0 & S^{(1)} + S^{(2)} \end{bmatrix} = \\ \begin{bmatrix} I & 0 & A_{II}^{(1)^{-1}}A_{IB}^{(1)} \\ 0 & I & A_{II}^{(2)^{-1}}A_{IB}^{(2)} \\ 0 & 0 & I \end{bmatrix} $$ Putting all that together, we have found that $$ \begin{bmatrix} A_{II}^{(1)} & 0 & 0 \\ 0 & A_{II}^{(2)} & 0 \\ 0 & 0 & S^{(1)} + S^{(2)} \end{bmatrix}^{-1}E_2E_1 A = \begin{bmatrix} I & 0 & A_{II}^{(1)^{-1}}A_{IB}^{(1)} \\ 0 & I & A_{II}^{(2)^{-1}}A_{IB}^{(2)} \\ 0 & 0 & I \end{bmatrix}. $$ Solving for $A$ yields $$ A = [E_1^{-1}E_2^{-1}]\begin{bmatrix} A_{II}^{(1)} & 0 & 0 \\ 0 & A_{II}^{(2)} & 0 \\ 0 & 0 & S^{(1)} + S^{(2)} \end{bmatrix}\begin{bmatrix} I & 0 & A_{II}^{(1)^{-1}}A_{IB}^{(1)} \\ 0 & I & A_{II}^{(2)^{-1}}A_{IB}^{(2)} \\ 0 & 0 & I \end{bmatrix}, $$ which is the block-factorization from (2).

As for why this kind of factorization would be useful, I'm guessing the intent is to speed up the computation of $A^{-1}$. Note that when $A = PQR$, we have $A^{-1} = R^{-1}Q^{-1}P^{-1}$. The individual inverses $P^{-1}, Q^{-1}, R^{-1}$ are relatively quick to compute due to the nice structure that each matrix has.