0
$\begingroup$

Consider the following linear system of equations: $$ \textbf{A}\textbf{x} = \textbf{b} $$ Where $\textbf{x}, \textbf{b} \in \mathbb{R}^{n}$ and $\textbf{A} \in \mathbb{R}^{n \times n}$. We also have that $\textbf{A}=\textbf{L}\textbf{U}$ where $\textbf{L} \in \mathbb{R}^{n \times m}$ and $ \textbf{U} \in \mathbb{R}^{m \times n}$ are non-square matrices ($m > n$). $\textbf{L}$ is constructed from a square lower triangular matrix $\textbf{L}_0 \in \mathbb{R}^{m \times m}$ by removing some of its rows, and $\textbf{U}$ is constructed from a square upper triangular matrix $\textbf{U}_0 \in \mathbb{R}^{m \times m}$ by removing some of its columns. The indices of the removed rows and columns are the same.

My questions are the following:

  • If $\textbf{A}$ is full rank, how can I use $\textbf{L}$ and $\textbf{U}$ to solve the linear system in $\mathcal{O}(n^2)$?

  • If $\textbf{A}$ is NOT full rank, how can I use $\textbf{L}$ and $\textbf{U}$ to find the least squares soluton of the system in $\mathcal{O}(n^2)$?

EDIT: Complexity $\mathcal{O}(m^2)$ is also acceptable in both cases.

$\endgroup$
  • $\begingroup$ Can't you extend L and U back to square form and use standard results for LU? Btw, it looks like in L you can only drop columns (not rows as you mention) $\endgroup$ – VorKir Dec 17 '18 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.