# Solving an upper triangular system of linear equations

Mathematics Asked by J.Ricky on December 1, 2020

Given

$$(I+T_1T_2T_3),x = b$$

where $I$ is the identity matrix and $T_1$, $T_2$ and $T_3$ are invertible upper triangular matrices. Matrix $(I+T_1T_2T_3)$ is also invertible. I want to know what the fastest method to find vector $x$ is.

I know that it is easy to

1. Find $A = I + T_1T_2T_3$ with $mathcal{O(n^3)}$ basic arithmetic operations.

2. Find $A^{-1}b$ with $mathcal{O(n^2)}$ basic arithmetic operations.

As a result it needs $mathcal{O(n^3)}$ operations. I wonder if it is possible to do it with $mathcal{O(n^2)}$ operations?

Note: I updated the question by adding the invertible matrix $T_3$. For case of two matrices, we can write the LHS, in form of $T_1^{-1}(T_1^{-1}+T_2)x$, which needs $mathcal{O}(n^2)$ operations to solve.

This answers the question for the case that $T_3 = I,$ which was my original question and I am writing it because Carl asked me.

Fact: For the invertible upper triangular matrix $T_1$, we need $O(n^2)$ operations to find its inverse.

Finding $x$ is equivalent to solving the following equation:

$$(T_1^{-1}+T_2)x = T_1^{-1}b.$$ Using the fact above, computing the upper-triangular $(T_1^{-1}+T_2)$ needs $O(n^2)$ operations. Finding $T_1^{-1}b$ needs $O(n^2)$ operations as well. Since $(T_1^{-1}+T_2)$ is upper-triangular, we can find $x$ from equation above with another $n^2/2$ operations.

Answered by J.Ricky on December 1, 2020

One thing you can do to avoid assembling the left hand side matrix if it is the $T_1T_2$ matrix multiplication you are afraid of:

Try a Krylov subspace method like conjugate residuals. Then in each iteration you can do a series of sparse matrix-vector multiplications instead. It will be linear in number of $T_k$ matrix factors so only $n^2/2$ multiplications times something unrelated to $n$ : will still be $O(n^2)$ - for each iteration. However the number of iterations we need for convergence can in worst case be $n$, which lands us with $O(n^3)$ in worst case. But there can be a huge difference between worst case and average case. Often Krylov methods converge to a useful solution in a very small fraction of $n$.

Here is the number of scalar multiplications per element of the product matrix

$$left[begin{array}{cccc}1&2&3&4\0&1&2&3\0&0&1&2\0&0&0&1end{array}right]$$

It sums up to $20$ for this $4times 4$ matrix compared to $4^3=64$. Given this structure how can we derive a formula for it?