Solving an upper triangular system of linear equations

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.

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?