Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [numerical-linear-algebra]

Questions on the various algorithms used in linear algebra computations (matrix computations).

Questions tagged with this tag can be about, but not limited to:

  1. Matrix decompositions like SVD, QR, Cholesky, etc.
  2. The solution of linear systems and least squares problems.
  3. Analysis of numerical linear algebra algorithms like condition numbers and stability analysis.
  4. Eigenvalue problems.
  5. The designs of direct or iterative methods to solve linear systems.
3541 questions
2
votes
0 answers

Check efficiently whether space becomes bigger

Consider a finite-dimensional vector space $V_{n - 1} = \langle v_1, \dots, v_{n-1}\rangle \subseteq V$. Let $v_n \in V$. Extend $V_{n-1}$ by $v_n$ ($V_n := \langle v_1, \dots, v_n \rangle$). The question is: How are we able to efficiently check…
user7427029
  • 719
2
votes
2 answers

Find matching columns between two matrices.

I have two $\mathbb{C}$ matrices $A$ and $B$. Matrix $A$ is $M \times N$. Matrix $B$ is $M \times R$. For each column in $B$, I want to find the column in $A$ that is most similar, i.e. minimize the difference. I have thought of two ways to go about…
ckwhite
  • 21
2
votes
0 answers

Growth factor of symmetric positive definite matrix

Let $A$ be symmetric positive definite matrix, and LU decompose it. Then we get $A = LL^T$. The growth factor of matrix A is as follows $$ \rho \equiv \frac{\max _{i, j}\left|u_{i j}\right|}{\max _{i, j}\left|a_{i j}\right|} $$ A textbook said that…
alryosha
  • 563
2
votes
1 answer

Orthogonal Projection in Arnoldi iteration.

Let $H_n$ be n x n Hessenberg matrix, $K_n$ be nth order Krylov subspace, and $Q_n$ be the orthogonal matrix resulting from QR decomposition of $K_n$. Then, at the nth step of Arnoldi iteration, we get the following equation. $$ H_n = Q_n^* AQ_n$$ I…
alryosha
  • 563
2
votes
2 answers

How to find a sparse basis of the null space of a large sparse matrix using QR decomposition

Suppose that we have a large sparse matrix $A\in{\mathbb{C}}^{m\times n}$, $m>m$, $\dim(V)=n-m$ is large. How to…
Wei Jiang
  • 77
2
votes
0 answers

initializing a guess when solving a linear system

Suppose I want to solve $Ax = b$ with an iterative method (I'm specifically thinking CG, so we're minimizing $\phi(x) := x^T A x - b^Tx,\, A \succ 0$). I was told to start my initial guess at $x_0 = 0$, but I don't understand why. If I'm using CG,…
jjjjjj
  • 2,671
2
votes
1 answer

Matrix Condition Number Definition

Wikipedia lists the condition number at x of any function $f: V_1 \rightarrow V_2$ between Banach spaces to be $\lim_{\epsilon\rightarrow 0^+} \sup_{||\delta x|| \le \epsilon} \left[ \frac{||f(x+\delta x) -f(x)||}{||f(x)||} / \frac{||\delta…
J Doe
  • 21
2
votes
0 answers

commuting a LU factorisation

Consider the permutation matrix $P= \begin{pmatrix} 0 & \cdots & 0 & 1 \\ 0 & \cdots & 1 &0 \\ \vdots & \ddots & \vdots & \vdots \\ 1 & \cdots & 0 & 0 {} \end{pmatrix}$ SoI showed that if $L$ is lower triangular then $PLP$ is upper…
Moritzplatz
  • 1,521
  • 14
  • 28
2
votes
1 answer

QR factorization

So I'm trying to factorize this matrix. $A= \left( \begin{array}{ccc} 3 & 0 \\ 0 & 3 \\ 4 & 0\\ 0&4 \end{array} \right)$ So I need to remove the 4 at $a_{1,3}$, however I'm a bit confused on how to best do it. I know Householder factorization, but…
simplicity
  • 3,694
2
votes
0 answers

Determinant of identity plus L^T L

Let $L$ be an invertible lower triangular $n\times n$ matrix and $I_n$ the identity matrix of size $n$. The determinant of $L$ can be computed efficiently in $O(n)$ time (vs $O(n^3)$ for arbitrary determinants). Is there an efficient way to compute…
Vokram8
  • 341
2
votes
0 answers

Relation on Krylov Spaces

Let $ K_n = \operatorname{span}\{b,Ab,\ldots,A^{n-1}b\} $. Also, show that $AK_n \subset K_n$ and $K_n = K_{n+1} = \cdots$. These spaces are odd to me. Any ideas how to prove this?
clocktower
  • 1,447
2
votes
0 answers

what's the difference between Eisenstat trick and an implicit preconditioner?

Assume ${A}$ is Hermitian positive definite and $\hat A$=$D^{-1/2}$$A$$D^{-1/2}$ is to obtain a symmetric variant. and $M$=($L_{A}$+$D$)$D^{-1}$($D$+$U_{A}$) where $D$ is a suitable diagonal matrix and $A$= $L_{A}$+$U_{A}$+$D_{A}$, so how much…
Lazar
  • 31
2
votes
0 answers

Looking for matrices such that $\kappa(A) =1$

Looking clues for this problem. Find all the matrices such that $\kappa(A) = 1$ We define $\kappa(A) = \|A\|\,\|A^{-1}\|$. If I'm looking matrices such that $\kappa(A) = 1$, I was thinking in this: 1) If $A = I$, the identity matrix, then…
Alexei0709
  • 1,184
2
votes
1 answer

Successive over-relaxation vs conjugate gradient

What is the advantages of successive over-relaxation and conjugate gradient methods over each other? When should I use one of them over the other? Here the discussion is limited to solving linear systems, since to my knowledge conjugate gradient…
Yuelong
  • 21
2
votes
2 answers

A proof of the uniqueness of svd?

I understand the geometric intuition, but the proof by induction in Trefethen book confuses me : it seems to me that a 1*1 complex matrix has infinitely many left and right singular vector pairs? The actual statement in the book is : "If A is…
yong
  • 35
1 2
3
…
11 12