# Questions tagged [lu-decomposition]

The tag has no usage guidance.

60 questions
0answers
26 views

### LU decomposition of matrix product

Let $A_1=L_1U_1$ and $A_2=L_2U_2$ be two matrices with their respective LU-factorizations ($L_i$ is lower triangular and $U_i$ upper triangular). Is it possible to obtain the LU decomposition of the ...
0answers
19 views

### Given the Cholesky decomposition of $A$, compute efficiently Cholesky decomposition of $RAR^T$?

Let $B = RAR^T$, where $A$ is positive definite and symmetric, and $R$ a generic matrix (possibly rectangular). Suppose I know the Cholesky decomposition $A=LL^T$. Is it possible to compute the ...
0answers
11 views

### Schur complement in LUP decomposition of a block tridiagonal matrix

Section 2.2 of the article On twisted factorizations of block tridiagonal matrices explains how to do a LUP decomposition of block tridiagonal matrices by showing the process on a 4 blocks by 4 blocks ...
0answers
28 views

### Using LU Decomposition to find determinants

I've been trying to find advantages and disadvantages to using LU factorisation with pivoting to compute determinants. There's a lot of information on its usefulness in regards to solving systems of ...
1answer
62 views

### How can I find partial pivoting matrix $P$ from $PA=LU$ decomposition if we know $A,L,U$?

Assume that we have this equation $$PA=LU$$ Where $A \in \Re^{mxn}$, $L \in \Re^{mxn}$ is a lower triangular matrix and $U \in \Re^{nxn}$ is an upper triangular matrix. $P \in \Re^{mxm}$ is the ...
0answers
44 views

### Numerical analysis, pivoting and incomplete LU decomposition

When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is, ...
1answer
39 views

### How can I find the pivot matrix from LU-factorization?

I trying to solve LU-factrization with pivoting: $$PA=LU$$ By using the subroutine sgeft2 from Lapack. It's a Fortran 90 library for numerical linear algebra. I have found the $L$ and $U$ matrix, ...
2answers
42 views

### Is there any way to use matrix decomposition for finding $A^n$?

If I want to take the power of matrix $A$ with e.g 3, $A^3$ or with power of $-\frac {1}{2}$, e.g $A^{-\frac {1}{2}}$ etc. Is there an easy way to solve $A^n$, where $n\in R$ and $A \in R^{nxn}$ by ...
0answers
18 views

### The decomposition for a symmetric positiv definite matrix is unique

We have the matrix \begin{equation*}A=\begin{pmatrix}1/2 & 1/5 & 1/10 & 1/17 \\ 1/5 & 1/2 & 1/5 & 1/10 \\ 1/10 & 1/5 & 1/2 & 1/5 \\ 1/17 & 1/10 & 1/5 & ...
1answer
78 views

### Which one is most cost expensive to solve a linear equation? LU or inverse?

Which one is the most expensive way to solve for linear equation? LU-decomposition $$A = LU$$ Or finding the inverse $$A^{-1} = \frac{1}{\det(A)} \operatorname{adj}(A)$$ If I have to choose, I ...
0answers
15 views

### Recursive QR-factorisation for N4SID - What does this equation mean?

I was reading a paper about recursive subspace identification, where they are using N4SID-algorithm with some extantion for the recursive method. http://www.iaescore.com/journals/index.php/IJEECS/...
0answers
75 views

### Proof of existence of LU-decomposition

I have a question concerning an existence proof of the $LU$-decomposition. The proof is as follows: If $E_{ij}$ denotes the matrix with $1$ at row $i$, column $j$ and zeros elsewhere then I let $P$ ...
2answers
45 views

### I want to know $PA=LU$ , what is $P$??

I know that if there is a $0$ in the diagonal, I use multiply $P$ to $A$. But, I saw the use of $P$ even if there was no zero. I want to know what $P$ is and what role it is for.
0answers
41 views

### Linear system with Non-square LU factors

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 ...
1answer
51 views

2answers
151 views

### Factorization of matrices over GF$(2)$

Suppose $A\in \mathbb{F}_2^{n\times n}$ is full rank non-symmetric matrix. Then, can we write $A=BB^T$ for some full-rank $B$? I know there exists a Cholesky factorization, but its not clear if that ...
1answer
35 views

### Sparse Matrix inversion some time singular some time get a big value

I want to invert a matrix which is a "band" diagonal matrix. The structure of the matrix is The blue strip represents the elements that are non zero.All other element in white area are of zero value. ...
1answer
73 views

### In QR and LU factorizations what would the results be with transposed inputs?

I really wish column-major matrix order was never invented. It very quickly stops making sense after two dimensions and now I have to deal with it when interfacing with the cuSolver functions. The ...
1answer
380 views

### How SVD for the frobenius norm has been calculated?

From the paper for Generalized low-rank models by Stephen Boyd, this Frobenius loss function has been used using SVD. Can someone explain it to me the following equation? Is U inverse is equal to U ...
1answer
445 views

### What is the computation time of LU-, Cholesky and QR-decomposition?

I found these information about computation-time of following decompositions: Cholesky: (1/3)*n^3 + O(n^2) --> So computation-time is O(n^3) LU: 2*(n^3/3) --> So computation-time is O(n^3) also (not ...
2answers
328 views

### Why (which advantages) we use different matrix factorization algorithms?

For the case of PA=LU factorization, I found some documents which tell that it may delete the probability of having 0's on the diagonal of Matrix A. But I am not sure if I got it right. If so, what is ...
1answer
340 views

### Cost of LU decomposition (time cost)

After calculation of the cost of the steps of the LU decomposition, and we come to the end result: $(2/3)n^3 - (2/3)n$ and we say the total cost is then $(2/3)n^3$ (ignoring the term $(-2/3)n$), ...
0answers
106 views

### LU/LUP decomposition: can some of U's diagonal elements be zero?

I'm learning LUP decomposition. So far I've wrote Doolittle implementation in GNU Octave: ...
0answers
91 views

### Cost of LU decomposition of a Symmetric Matrix

I have this question: what is the cost of computing LU decomposition for a symmetric matrix. I tried to compute it, however, I calculated it as $2n^2$ as follows: I considered the LDL decomposition, ...
0answers
160 views

1answer
111 views

1answer
4k views

1answer
875 views

### Complexity/Operation count for the forward and backward substitution in the LU decomposition?

If I have a linear system of equations $Ax=b$ where $A \in \mathbb{R} ^{n\times n}, x \in \mathbb{R} ^{n}, b \in \mathbb{R} ^{n}$ this system can be solved for $x$ via an LU decomposition: $$A = LU$$ ...
2answers
512 views

### LU-decomposition of A

I have: $A=\begin{bmatrix} 2 & -1 & 2 & 3 & 4 \\ 4 & -2 & 7 & 7 & 6 \\ 2 & -1 & 20 & 9 & -8 \end{bmatrix}$ and I'm asked to LU-decomposition A, then ...
1answer
59 views

### Large scale system of equation where $A \in {\rm I\!R}^{n\times n}$ is too large for main memory

Assuming I have, on a secondary memory like SSD, a matrix $A \in {\rm I\!R}^{n\times n}$ that is very large and cannot be stored on the main memory. I want to compute a (virtually) upper triangular ...
1answer
463 views

### LU decomposition without pivoting for symmetric definite negative matrix?

While studying LU decomposition from this book I came across the statement that pivoting in LU decomposition is not necessary in some cases, as for example when the matrix is symmetric positive ...
1answer
958 views

### Why we use LDU factorization rather than LU factorization?

Why people make and use LDU factorization? I think LU factorization and PA = LU are enough to solve equation. Anyone know why?
0answers
35 views

### Solving for $I- A$ based on LU factorization of $A$

Suppose I have the LU factorization for a given matrix $A$ ($A$ is not symmetric positive definite), then is there a faster way to solve for $x$ in the following equation, as compared to doing LU all ...
3answers
543 views