Solving an upper triangular system of linear equations 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


*

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

*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.
 A: 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&1\end{array}\right]$$
It sums up to $20$ for this $4\times 4$ matrix compared to $4^3=64$. Given this structure how can we derive a formula for it?
A: 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.
