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.

0
votes
0answers
18 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
59 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
42 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
34 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
39 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
16 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
53 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
14 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
63 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
37 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
37 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
44 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
34 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
51 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
51 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
38 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
70 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
53 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
140 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
33 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
70 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
339 views

How SVD for the frobenius norm has been calculated?

![From the paper for Generalized low-rank y 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
364 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
295 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
302 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
102 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
90 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
147 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
79 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
101 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
56 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
164 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
465 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
111 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 &...
1
vote
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
229 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
771 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
503 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
453 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
912 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
525 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
305 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
278 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
266 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
508 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
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 ...
1
vote
1answer
164 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} ...