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
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 ...
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 ...
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 ...
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
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, ...
1
vote
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, ...
2
votes
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 ...
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 & ...
2
votes
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 ...
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$ ...
1
vote
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.
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 ...
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 \...
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
60 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 ...
1
vote
0answers
52 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 ...
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 ...
2
votes
1answer
81 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 ...
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 $|{...
1
vote
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 ...
0
votes
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. ...
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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$), ...
1
vote
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: ...
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, ...
1
vote
0answers
160 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 ...
0
votes
1answer
80 views

Is it okay transposing each matrix elements?

I'm learning about LU decomposition with a math book, but this question is not about LU decomposition, just wanted to explain why am I wondering about this. We assume that $A$ is $m×n$ matrix, and $s ...
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 ...
-1
votes
1answer
58 views

Creating a matrix in Julia [closed]

I'm having trouble creating this matrix in Julia. I need to find the LU factorization, which I believe I know the code for. Should I be choosing my own $n$ here?
2
votes
0answers
168 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, ...
1
vote
2answers
487 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 ...
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 &...
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
0answers
254 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 $\...
3
votes
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$$ ...
3
votes
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 ...
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 ...
2
votes
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 ...
1
vote
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?
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 \...
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 ...
1
vote
0answers
292 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, ...