Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lu-decomposition]

The tag has no usage guidance.

1
vote
3answers
543 views

Solving System of Linear Equations with LU Decomposition of $4 \times 3$ matrix

The following is all confirmed to be true: Matrix A = $ \begin{bmatrix} 0 & 1 & -2 \\ -1 & 2 & -1 \\ 2 & -4 & 3 \\ 1 & -3 & 2 \...
1
vote
1answer
961 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?
1
vote
1answer
853 views

Complexity of LUP decomposition of tri-diagonal matrix to solve an equation?

Doing LU decomposition of tri-diagonal matrix and then solving the eqn by using forward substitution followed by backward substitution is done is O(n) time. http://www.cfm.brown.edu/people/gk/chap6/...
0
votes
1answer
35 views

LU decomposition of a matrix given LU decomposition of its blocks.

Suppose $A, B, C$ are $n\times n$ matrices. Let $A = L_1U_1$ and $D = L_2U_2$. Then what is the LU decomposition of $$\begin{bmatrix} A&B\\ 0&D\end{bmatrix}$$ How to find this? I am able to ...
0
votes
1answer
39 views

Given LU decomposition of matrix A, How to solve $(A-uv^T)x=b$?

Homework disclaimer... 9 tasks for homework, out of which 6 required, out of which I can solve 4 but have no idea what to do with the other 2. This is one of these 2. Given the decomposition $PA=LU$...
0
votes
1answer
446 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 ...
0
votes
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 ...
0
votes
1answer
343 views

reasons for error in lu decomposition

This is a very general question. Let's assume i have 3 pairs of point correspondences $(p_i, q_i)$ with real coordinates an i want to compute the transformation matrix that transforms the point $p_i$ ...
2
votes
0answers
169 views

inverting a matrix using the LU decomposition approach

I have written the Matrix class in cython for the matrix inversion and some other linear algebra operations. I tried to use the LU decomposition and forward, ...
2
votes
0answers
257 views

Simultaneous LU and UL decomposition

It is known that a square, invertible matrix $\mathbf{A}$ always has a LU decomposition, after possibly a column permutation, i.e., $$ \mathbf{A} \mathbf{P}_C = \mathbf{L}_1 \mathbf{U}_1 $$ where $\...
1
vote
0answers
29 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 ...
1
vote
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 ...
1
vote
0answers
47 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, ...
1
vote
0answers
53 views

Updating Cholesky decomposition when deleting one row and one and column.

I found the answer of updating Updating Cholesky decomposition when deleting one row and one and column on Cholesky decomposition when deleting one row and one and column. Is there any generalisation ...
1
vote
0answers
109 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: ...
1
vote
0answers
162 views

Why WolframAlpha does LU decomposition with pivoting even when it isn't needed?

I want to do LU decomposition with $A$: $ A= \left[ {\begin{array}{cc} 1 & 2 & 3 & 4 \\ -9 & 8 & -15 & 4 \\ 2 & 13 & -21 & 7 \\ 4 & -5 & 5 ...
1
vote
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 ...
1
vote
0answers
293 views

Column spaces of lower triangular matrix in LU decomposition with partial pivoting

I am studying $LU$ decomposition with partial pivoting in Numerical Linear Algebra book. I have a problem in understanding the discussion on $L^{-1}$ in lecture 22.(Original paragraph is attached as ...
1
vote
0answers
276 views

Partial LU decomposition and the space spanned by matrix L

In partial $LU$ decomposition of a $n \times n$ matrix A, we have $LU = PA$. $P$ is a $n \times n$ permutation matrix. $L$ and $U$ are $n \times n$ lower and upper triangular matrices, ...
1
vote
0answers
519 views

An algorithm for Cholesky factorization

I am studying the lecture 23 in Numerical Linear Algebra book and I cannot follow the part that explains the Cholesky Factorization's algorithm. Specifically it is written: When Cholesky ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 & ...
0
votes
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/...
0
votes
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$ ...
0
votes
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 ...
0
votes
0answers
54 views

Which is the correct one?

Here is an excerpt from the book 'Applied Numerical Linear Algebra' by James W. Demmel from SIAM But I have done it slightly different taking $\hat{l}_{ij}$ and $\hat{u}_{ij}$ and ended up getting $|{...
0
votes
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, ...
0
votes
0answers
122 views

PLU decomposition, when num. stability requires complete pivoting

I found this example both in class and in a book, but I'm struggling to understand why is the regular LU decomposition problematic here. Given a matrix $$A=\left(\matrix{1 & 0 & 0 & 0 &...
0
votes
0answers
20 views

Incorrect theorem in preparation for polar decomposition in notes?

Theorem 2.3 here says that if $A$ is normal it has a positive semi-definite square root. Isn't this wrong? In particular the fourth sentence of the proof claims the eigenvalues of normal matrices are ...