1
vote
0answers
42 views

Lanczos algorithm with thick restart on a dynamic matrix

currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...
3
votes
0answers
68 views

What do we know about the generalized eigenvalue problem involving a projector?

Consider a matrix $A\in\mathbb{R}^{n\times n}$ and a projector $P\in\mathbb{R}^{n\times n}$. Are there results regarding the generalized eigenpairs $(v,\lambda)$ of the generalized eigenproblem ...
0
votes
0answers
47 views

Generalized Eigenvalue problem solution

$\circ$ Consider the following eigenvalue problem : $$XY^{T}YX^{T}w=\lambda XX^{T}w \hspace{0.5cm} (1)$$ Matrices $XY^{T}$ and $XX^{T}$ $\in \mathbb{R}_{n \times n}$ are positive semi-definite and ...
1
vote
0answers
94 views

Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix

I am looking mainly for implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers. To be precise, I want ...
1
vote
1answer
53 views

Augmenting orthonormal system into complete orthonormal system in a numerically stable way

Let us suppose we have a, say, 10 dimensional real space with 3 orthogonal unit vectors given. How do I complete this orthonormal system with 7 additional vectors into a complete ONS in a way that is ...
1
vote
0answers
40 views

Nontrivial Matrix-estimate

I try to proof the following estimate: \begin{align} h' W^{-1} H W^{-1} h \geq c h' H h \qquad c>0, \qquad\qquad (1) \end{align} where $h\in\mathbb{R}^{K-1}$ and ...
1
vote
1answer
122 views

Eigenvalue problem with quadratic constraints

$\circ$ Consider the following eigenvalue problem : $$Ax=\lambda x \hspace{0.5cm} (1)$$ where matrice $A \in \mathbb{R}_{n \times n}$ is a positive semi-definite with eigenvectors $x = ...
2
votes
1answer
79 views

Updating $LU$ decomposition after adding a sparse matrix

How many elements of $LU$ decomposition of a symmetric matrix change after adding a sparse symmetric matrix? Is it more efficient to recompute $LU$ decomposition after adding a sparse matrix comparing ...
11
votes
2answers
401 views

How to project a vector onto a very large, non-orthogonal subspace

I have a difficult problem. I have a very large, non-orthogonal matrix $A$ and need to project the vector $y$ onto the subspace spanning the columns of $A$. If this were a small matrix, I would use ...
4
votes
0answers
94 views

Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D ...
2
votes
1answer
154 views

Possible pathological properties of positive definite matrix

Suppose $A$ is a positive definite matrix such that $$I \preceq A \preceq 1.01I.$$ Is it possible that $$\sum_{i=1}^n A_{1i}$$ can be arbitrarily large? Thanks, Jack
7
votes
0answers
115 views

Problems where Conjugate gradient works much better than GMRES

I am interested in cases where Conjugate gradient works much better than GMRES method. In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound ...
10
votes
2answers
348 views

Computing a large permanent

Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix? I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices ...
7
votes
1answer
131 views

Who first observed that Conjugate Gradient for Symmetric Positive Definite linear systems is a Krylov method?

Conjugate gradient was originally presented in the 50's before the modern understanding of Krylov subspaces (and the resulting iterative methods) was fully realized. As such, the method was derived ...
4
votes
1answer
591 views

Efficient computation of Markov chain transition probability matrix

Consider a continuous Markov chain $X = (X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...
1
vote
1answer
154 views

integral basis of orthogonal complement

Suppose there are $r$ linearly independent vectors $v_1,\dots,v_r\in \mathbb{R}^n$, all of them have integer-valued entries and $\|v_i\|_\infty\leq m$ for some integer $m$. My goal is to find an ...
0
votes
1answer
76 views

Avoiding epsilon in mixed integer linear and quadratically constrained programs

I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$. $(x = 0 \wedge y = 1) \vee (x \neq 0 ...
4
votes
1answer
210 views

best rank r approximation for non-Frobenius norm

The best rank $r$ approximation to a given matrix $M$ in Frobenius norm, according to Eckart-Young theorem, is truncated SVD - just keep $r$ largest singular values. What if I need to construct best ...
4
votes
1answer
491 views

Matrix perturbation theory

I am having matrix $M_0$ with coresponding eigenvectors and 4 eigenvalues {0,0,a,-a}. Eigenvalue $\lambda=0$ is double degenerated. Now I am appliing small perturbation $\epsilon M_1$ and want to get ...
3
votes
1answer
89 views

Kronecker-structured matrix kernel

Let $A,B\in\mathbb{C}^{n\times 3n}$ be two matrices, and denote the Kronecker matrix product by $\otimes$. The matrix $$ M= \begin{bmatrix} A \otimes I_n \\\\ I_n \otimes B\end{bmatrix} $$ has size ...
4
votes
0answers
45 views

Recovering Shared Eigenvector Set

Suppose we are given a set of $M$ pairs $\{(\vec{x}^{(i)},\vec{y}^{(i)})\}$, with $\vec{x}^{(i)}\in\mathbb{R}^N$, $\vec{y}^{(i)}\in\mathbb{R}^N$, $M\gg N$ such that $\vec{y}^{(i)} = Q^{(i)} ...
5
votes
0answers
131 views

Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently

Hi, my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$. The matrix $C$ is huge ($n$ up to a ...
13
votes
2answers
287 views

Condition number of matrix after partial orthogonalization

I'm wondering about which bounds one can put on the condition number of a $n\times n$ square matrix which is obtained from another $n\times n$ square matrix by orthogonalizing the first $m < n$ ...
1
vote
0answers
97 views

Matrix Minimax problem

I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The ...
4
votes
1answer
299 views

Norm of inverse confluent Vandermonde matrix

Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as $$V= \begin{bmatrix} ...
2
votes
0answers
133 views

Checking for error in conjugate gradient algorithm

What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...
4
votes
1answer
1k views

Upper bound on largest eigenvalue of a real symmetric n*n matrix with all main diagonal >0, everywhere else <=0

Is there a good analytic upper bound on the largest eigenvalue of a real symmetric n*n matrix with all main diagonal entries strictly positive, all other entries <=0 with typically many of them ...
1
vote
0answers
57 views

Is there a Krylov subspace method for solving D+epsilon*S where D is diagonal, epsilon small and S skew-symmetric

I'm working on a problem that gives a matrix system of the form D + epsilon*S, where S is a skew-symmetric matrix. I'm interested in finding if any work has been done to develop a conjugate gradient ...
5
votes
3answers
445 views

solving Lyapunov-like equation

The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
0
votes
1answer
159 views

Ease of calculation of norm

I have SPD matrix A and two vectors z and b. Is there exist a norm where I can calculate $||A^{1/2}b-z||$ without having to calculate $A^{1/2}b$ explicitly ?
5
votes
0answers
124 views

reference for perturbation of projection result

Let $A$ and $B$ have the same rank and dimensions. If $P_A$ denotes the projection onto the range space of $A$, then $$ \|P_A - P_B\|_2 \leq \|A - B\| \cdot \min (\|A^\dagger\|_2, \|B^\dagger\|_2). $$ ...
0
votes
1answer
215 views

Moore-Penrose bound question

Suppose that we are given an equation $Ax=b$. The minimum least-squares solution is of course $x_{m}=A^{\dagger}b$. What I want to know is whether there are known bounds on $||x-x_{m}||$. In the ...
2
votes
2answers
362 views

A sum of eigenvalues

Let $X$ be an $n\times n$ symmetric matrix. Suppose $\lambda_1(X)\geq \lambda_2(X) \geq \cdots \geq \lambda_n(X)$ are eigenvalues of $X$. Let $r$ be any integer with $1\leq r\leq n$. It is well-known ...
1
vote
1answer
292 views

sign-flipping inverse

Consider this matrix: $Z=\begin{bmatrix}23.9 & -7 & -17 \\\\ -7 & 23.9 & -17 \\\\ -17 & -17 & 33.9 \end{bmatrix}$ Its inverse is entrywise negative (you can check...) and ...
2
votes
1answer
222 views

A question for solutions of perturbed linear systems

Consider a linear system $$Ax=b\qquad (*)$$ and a sequence of perturbed linear systems $$(A+\delta A_n)x=b+\delta b_n. \qquad (n)$$ Suppose that all the linear systems are consistent (i.e., ...
3
votes
0answers
108 views

Computing the norm of the columns of an implicitly defined matrix

I have an $n \times n$ matrix $M = \Sigma W$ where $\Sigma$ is diagonal and $W$ orthogonal. $W$ is implicitly defined, i.e. I can only perform matrix-vector products (but I also have access to $W^T$). ...
1
vote
3answers
163 views

Solving for an operator by minimization

Please note that I am looking for numerical algorithms that will tell me what the operator is that minimizes a problem. I have a 2x2 complex hermitian operator that is a function of two variables, so ...
2
votes
2answers
503 views

sparsity of QR decomposition

Hi, everyone! I have a sparse $n \times n$ matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in $A$. Now I use QR factorization to decompose $A$ into an orthogonal matrix $Q$ and ...
2
votes
1answer
122 views

Relations between a set of inner products of vectors

Suppose we have n normalized vectors on an arbitrarily large Hilbert space $|A_1\rangle,\dots,|A_n\rangle$, $\langle A_i|A_i\rangle=1$ for every i. And there're $\frac{n(n-1)}{2}$ inner products ...
5
votes
1answer
418 views

Rank of the absolute-value matrix $|M|$ vs. rank of $M$

Let $M$ be a real matrix of rank $r$ (and let us set $M=UV^T$, with $U,V^T\in\mathbb{R}^{n\times r}$, to fix the notation). Let $|M|$ be the matrix obtained by taking the absolute value of each entry ...
5
votes
2answers
621 views

Factorizing a block symmetric matrix

Let $X,Y\in\mathbb{R}^{n\times n}$ be symmetric matrices. You may assume that $X$ is positive semidefinite and $Y$ negative semidefinite, if needed, but not that they are invertible. I would like to ...
7
votes
2answers
457 views

Efficiently computing a few localized eigenvectors

Let $H = \triangle + V(x) : \mathbb{R}^2 \rightarrow \mathbb{R}^2$. I am interested in domain decomposition for an eigenproblem involving $H$. The lowest 1000 eigenfunctions of $H$, $ \psi_i $, can ...
1
vote
0answers
181 views

Norm preserving matrix fix

Hello, I'll state the problem first and than I'll a little bit of motivation. Lets be given regular matrix $M \in \mathbb{R}^{n\times n}$ and norm $||.||$ in $\mathbb{R}^{n}$. Define $$ U =\{ L\in ...
1
vote
1answer
694 views

On an eigenvalue inequality

Let $\lambda_1 (\cdot)$ be the larger absolute value eigenvalue of a $2\times2$ matrix and $\lambda_2 (\cdot)$ the smaller absolute value eigenvalue of a $2\times2$ matrix, i.e. $|\lambda_1 (\cdot)| ...
2
votes
4answers
679 views

Fast multiplication of constant symmetric positive-definite matrix and vector.

Consider the matrix $H=H^T$, $H>0$, $H \in R^{n \times n}$, and the vector $v \in R^n$. In a numerical algorithm, I need to compute the product $b = Hv$. Right now I am following the naive ...
0
votes
0answers
186 views

Comparing iterative methods for linear systems

For a tridiagonal matrix of the from \begin{bmatrix} a & -b & \newline -b & a & -b \newline & \ddots & \ddots & \ddots \newline & & & & ...
2
votes
2answers
545 views

Eigenvectors of a diagonalizable matrix

Suppose we have a n-by-n symmetric matrix K which can be factorized in a way, K = H * L * H', where L is a m-by-m diagonal matrix and H is a n-by-m matrix. In addition, let's assume n <= m. Can we ...
7
votes
2answers
831 views

Algorithm for the smallest (algebraic) eigenvalues of a symmetric (sparse) matrix

Hi, I'm looking for a way to get the negative eigenspace of a large (sparse) symmetric matrix. This matrix is basically a discretized version of the operator $-\Delta + V$, $V$ negative, on some ...
5
votes
1answer
474 views

Special considerations when using the Woodbury matrix identity numerically.

Are there any special considerations when using the Woodbury matrix identity numerically? What is the best metric for numerical stability in this case? Can anyone point me to a good reference? The ...
2
votes
1answer
1k views

How to do (m)Gram-Schmidt orthogonalization with integers ? (real life problem) (“mathematicalized reformulation”)

New edition of the question, "mathematicalized" (thanks to Gerhard). Consider and integer valued n*n matrix M, with integers elements in the range -N < m < N. I want to find integer-valued ...