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.

4
votes
4answers
5k views

Is the $L$ in $LU$ factorization unique?

I was doing an $LU$ factorization problem \begin{bmatrix} 2 & 3 & 2 \\ 4 & 13 & 9 \\ -6 & 5 &4 \end{bmatrix} and I was going to multiply the second row by ...
4
votes
1answer
1k views

Cholesky decomposition when deleting one row and one and column.

I've thought about this problem for days but could not find a good answer. Given Cholesky decomposition of a symmetric positive semidefinite matrix $A = LL^T$. Now, suppose that we delete the $i$-th ...
3
votes
1answer
885 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$$ ...
3
votes
2answers
514 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 ...
2
votes
2answers
43 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 ...
2
votes
1answer
79 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 ...
2
votes
1answer
4k views

PA = LU Decomposition with Row Exchange

I am not sure how to deal with the L with we do row exchange in PA = LU decomposition. Here's my example: $ A = \left[ {\begin{array}{ccc} 1 & 1 & 1\\ 0 & 0 & 1\\ 2 &...
2
votes
1answer
84 views

LU Decomposition: difference between between hand calculation and solver?

I have a $3 \times 3$ matrix $A$ and have to perform the $LU$ Factorization (1) $$ A = \begin{bmatrix} 1 & 2 & 3 \\ 1 & -1 & 3 \\ -2 & -10 & -2 \end{bmatrix}$$ Using row ...
2
votes
1answer
165 views

$PA = LU$ descomposition. Prove that $\max_{1\leq i,j\leq n}|u_{i,j}| \leq 2\max_{1\leq i,j\leq n}|a_{i,j}|$

I am stuck on this problem: Let $A = (a_{ij}) \in \mathbb{C}^{n\times n}$ be nonsingular matrix. $a_{i,j} = 0$ for $|i −j| ≥ 2$ so matrix looks like this \begin{bmatrix} a_{11} & a_{12} ...
2
votes
1answer
994 views

LU Decomposition to Compute Rank

I am trying to understand how to use LU Decomposition to calculate the rank of a matrix. I tried googling, but I could not find any details except vague comments that lead me to believe that there is ...
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
258 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 $\...
2
votes
1answer
464 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 ...
1
vote
2answers
156 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 ...
1
vote
1answer
41 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, ...
1
vote
2answers
46 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.
1
vote
1answer
51 views

How to compute amount of floating point operations for LU-decomposition of banded matrix?

I want to compute the amount of floating point operations, flops, needed for the LU-decomposition/factorization of a banded matrix A consisting of 5 nonzero diagonals. Matrix $A\in\mathbb{R}^{n \...
1
vote
1answer
389 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 ...
1
vote
1answer
364 views

Find LU decomposition of a matrix using partial pivoting

I've the following matrix: $$ A= \begin{bmatrix} 0& 7& 5& 1 \\ 4& 3& 2& 1 \\0 &0& 0& 1 \\ 0& 0& -1& -2 \end{...
1
vote
0answers
30 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
20 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
13 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 ...
1
vote
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 ...
1
vote
0answers
48 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
111 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
163 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
2answers
492 views

Inverse of matrix, LU Decomp, A^-1 = U^-1 L^-1 Not true for all cases?

I have Matrix A A= A^-1= 1 2 0 -1 2 0 1 1 0 1 -1 0 0 0 1 0 0 1 Which forms the upper and lower matrices ...
1
vote
1answer
967 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
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
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
0answers
295 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
277 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
523 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 ...
1
vote
0answers
546 views

Pivot Matrix for Row Permutations in LU decomposition (C++/CUDA) [closed]

I'm trying to implement some determinant routines for some CUDA C++ code that I'm writing. The only issue is, my code is returning nan's and inf's! It turns out that it's my pivoting routine that's ...
1
vote
1answer
855 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
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 ...
0
votes
1answer
63 views

Optimal pivoting strategy in LU factorization

I'm currently reading the book Numerical Linear Algebra by Lloyd N. Trefethen and David Bau, III, working my way through the required lectures for my Numerical Analysis class. The current subject is ...
0
votes
2answers
335 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 ...
0
votes
1answer
111 views

LU Factorization. Finding L and A given y, b and U

In a question I am given this information: $$ U = \begin {bmatrix} 1 & 2 & 4\\ 0 & 1 & 1\\ 0 & 0 & 3\\ \end {bmatrix} $$ $$L \mathbf y = \begin {bmatrix} 3\\ 13\\ 4\\ \end ...
0
votes
1answer
317 views

LU Decomposition Determinant Mismatch Matlab

I'm trying to get the determinant of a matrix by LU factorization. I have the following matrix: a = [2 4 2; 1 5 2; 4 -1 9]; When I execute the command ...
0
votes
0answers
29 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
42 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
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
34 views

Finding first nonzero element per row after Choleski decomposition

For a symmetric and positive definite matrix $A$, we define the numbers $f_{i}(A), i=1,...,n$ as follows: $f_{i}(A)=min${${j|a_{i,j}\neq0}$} Show that for the Choleski decomposition $A=LL^{T}$ the ...
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 $|{...