Questions tagged [linear-algebra]
Questions on the algorithmic/computational aspects of linear algebra, including the solution of linear systems, least squares problems, eigenproblems, and other such matters.
128
questions
12
votes
0answers
534 views
Fast Eigenvalue and SVD Solver for Structured Matrices
I am looking for a fast Eigenvalue and SVD solver for small dense structured matrices (Hankel and Toeplitz). I have searched for efficient implementations in libraries like MKL but I am not able to ...
11
votes
2answers
3k views
Eigenvalue decomposition of the sum: A (symmetric) + D (diagonal)
Suppose $A$ is a real symmetric matrix and its eigenvalue decomposition $V \Lambda V^T$ is given. It is easy to see what happens with the eigenvalues of the sum $A + cI$ where $c$ is a scalar constant ...
10
votes
2answers
1k views
Which iterative linear solvers converge for positive semidefinite matrices?
I want to know which of the classic linear solvers (e.g Gauss-Seidel, Jacobi, SOR) are guaranteed to converge for the problem $Ax=b$ where $A$ is positive semi definite and of course $b \in im(A)$
(...
8
votes
1answer
670 views
Linear system solution with inequality constraints - methods?
First of all, I hope I am posting this in the correct place. If not, I'm sorry and could you please direct me to where I should post this?
Problem: You are given a set of vectors, $\{\mathbf{a}^i\}_{...
8
votes
1answer
416 views
Least-squares for a diagonal matrix
This is a follow-up to a different question I asked with more detail.
For $v\in\mathbb{R}^n$, denote $D_v\in\mathbb{R}^n$ as the diagonal matrix with elements in $v$. Given a "tall" matrix $B\in\...
7
votes
1answer
917 views
Sparse hermitian eigensystems: are there better techniques than Arpack or TRLan?
As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
6
votes
1answer
161 views
Computing square root of diag(u)-uu'?
I need an efficient way to take square root of a matrix which is a sum of diagonal matrix and rank-1 matrix.
More specifically it's the following matrix
$$A=D-uu'=\text{diag}(u)-uu'$$
Where entries ...
5
votes
1answer
239 views
CHOLMOD condition number estimate
The CHOLMOD library provides a CHOLMOD_rcond function that estimates the reciprocal condition number (in the one norm) of a symmetric positive definite matrix from ...
4
votes
2answers
1k views
Null Space Projection for Singular Systems
Let $A$ be a general symmetric matrix operator and $P$ be the unique orthogonal projection onto $\operatorname{Range}(A) = \operatorname{Null}(A)^\perp$.
Analytically, the system
$$Ax = Pb$$
should ...
2
votes
1answer
940 views
Doubt regarding stopping criterion for Newton method
I am solving an unconstrained convex optimization problem, which can easily have a million variables. I am trying to get a working system with a toy problem of around 200 variables. I am noticing that ...
15
votes
2answers
467 views
Is there any way to do “double preconditioning”
Question:
Suppose that you have two different (factored) preconditioners for a symmetric positive definite matrix $A$:
$$A \approx B^TB$$
and
$$A \approx C^TC,$$
where the inverses of the factors $B, ...
9
votes
4answers
2k views
Generating Symmetric Positive Definite Matrices using indices
I was trying to run test cases for CG and I need to generate:
symmetric positive definite matrices
of size > 10,000
FULL DENSE
Using only matrix indices and if necessary 1 vector
(Like $A(i,j) = \...
9
votes
3answers
4k views
Fastest algorithm to compute the condition number of a large matrix in Matlab/Octave
From the definition of condition number it seems that a matrix inversion is needed to compute it, I'm wondering if for a generic square matrix (or better if symmetric positive definite) is possible to ...
9
votes
2answers
1k views
Safe application of iterative methods on diagonally dominant matrices
Suppose the following linear system is given
$$Lx=c,\tag1$$
where $L$ is the weighted Laplacian known to be positive $semi-$definite with a one dimensional null space spanned by $1_n=(1,\dots,1)\in\...
8
votes
5answers
4k views
Minimizing $\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$ using CVX
In Matlab, I would like to minimize the function
$$f(S)=\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$$
where $S \in \mathcal{M}_{m,m}$ is symmetric and positive definite, which is definitely a convex ...
7
votes
1answer
3k views
What is the best way to multiply a diagonal matrix (in fortran)
What is the best way to compute:
$$ Y = D X $$
where $D \in \mathbb{R}^{m\times m}$ is diagonal and $X \in \mathbb{C}^{m \times n}$ is general. I am mostly interested in these two cases:
$m >> ...
7
votes
3answers
751 views
Solving shifted linear systems with LU factorization
I am interested in solving a sequence of shifted linear systems $(A+\sigma I)x = b$ for various values of $\sigma$. The matrix $A$ is sparse and not too large, so I have its LU factorization available....
7
votes
1answer
147 views
What are some ideas to preprocess / precondition the following linear system?
Let $A\in \mathbb{R}^{n\times n}$ symmetric and positive semidefinite, and $\omega\in \mathbb{R}\setminus\{0\}$. I am interested in solving the following linear system for a range of values of $\...
6
votes
0answers
126 views
What strategies / decompositions would be useful to solve the following linear system repeatedly if I only care about time to solution?
Let $A\in \mathbb{R}^{n\times n}$ be symmetric positive semidefinite, and $B\in \mathbb{R}^{n\times n}$ be symmetric positive definite. Suppose $B$ is block diagonal so it is easy to invert. (We ...
6
votes
2answers
6k views
Recommendations for a usable, fast Java matrix library?
This complements an earlier question on usable, fast C++ matrix libraries.
I've looked at the Java Matrix Benchmark, and it seems like the performance of java matrix libraries is all over the place. ...
5
votes
2answers
244 views
Solving “Hadamard systems”
Suppose we have two matrices $A$ and $B$ (we can assume they're symmetric; if absolutely necessary I think they may be positive definite). Then, is there any technique for solving $$(A\circ B)x=b,$$ ...
3
votes
2answers
2k views
How to find the nearest/a near positive definite from a given matrix?
I'm given a matrix. How do I find the nearest (or a near) positive definite from it?
The matrix can have complex eigenvalues, not be symmetric, etc. However, all its entries are real valued. The ...
3
votes
1answer
925 views
Spectral decomposition with eigenvalue shift
Suppose a square, real and symmetric matrix $G\in\mathbb{R}^{n\times n}$ is given, and it is known to have one zero eigenvalue associated with all ones eigenvector, $1_n$. I'm aware that the (possibly)...
3
votes
0answers
184 views
Find constrained vectors maximizing angles between them - methods?
This is related to a question I had asked earlier, with the distinction that earlier I did not have a non-linear objective functional to minimize. The problem is reproduced below with added ...
3
votes
2answers
154 views
Factoring the sum of two matrices
Given
\begin{equation}
A_i=B+C_i
\end{equation}
where $A_i$,$B$ and $C_i$, $i=1,\dotsc,N$ are large square matrices, $B$ is symmetric, $C_i$ are zero matrices aside for a square block on the diagonal.
...
3
votes
1answer
123 views
Analytic formula for leading eigenvector of $uu^T + vv^T$?
Let $u$ and $v$ be nonzero column vectors of size $n$ and consider the $n \times n$ positive-definite matrix $A:=uu^T + vv^T$. In this post https://math.stackexchange.com/a/112201/168758, the ...
3
votes
1answer
158 views
Implementation of a $O(n \log(n))$ method to compute eigenvalues of real symmetric tridiagonal matrices
I just came upon this paper, which details the implementation of a fast method to get eigenvalues of tridiagonal symmetric matrices :
Coakley, Ed S.; Rokhlin, Vladimir, A fast divide-and-conquer ...
3
votes
2answers
2k views
SVD of large block-hankel matrix
I am trying to do SVD of a large block-hankel matrix for model order reduction (Low rank approximation). However, I quickly run into memory issues in forming the large Block-Hankel matrix and CPU ...
2
votes
2answers
448 views
Precision loss in Matrix-Vector product when applying Finite-Difference scheme
I am applying a 6th order Finite-Difference differentiation scheme as seen in http://www.scholarpedia.org/article/Method_of_lines/example_implementation/dss006
There seems to be severe numerical/...
2
votes
3answers
344 views
Generating Random Orthogonal Matrices in C++
I'm looking for an open-source library for the generation of random n-dimensional orthogonal matrices in C++.
In python, it looks like such a function is available in the NumPy package. But I was not ...
1
vote
3answers
1k views
sorting adjacency matrix by the Fiedler vector
I have a fairly sparse adjacency matrix showing connections between approx 5,000 points in my dataset. I'm looking at various ways to analyze the relationships between the data points.
This approach ...
0
votes
1answer
63 views
Analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^T A z$, where $A=uu^T+vv^T$
Let $u$ and $v$ be column vectors of size $n \gg 1$ (not both zero), and consider the matrix $A:=uu^T+vv^T$
Question
What is an analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^TAz=\arg\max_{\|z\...
11
votes
4answers
2k views
Finding the square root of a Laplacian matrix
Suppose the following matrix $A$ is given
$$ \left[\begin{array}{ccc}
0.500 & -0.333 & -0.167\\
-0.500 & 0.667 & -0.167\\
-0.500 & -0.333 & 0.833\end{array}\right]$$
with ...
10
votes
2answers
1k views
Is the maximum/minimum principle of the heat equation maintained by the Crank-Nicolson discretization?
I'm using the Crank-Nicolson finite difference scheme to solve a 1D heat equation. I'm wondering if the maximum/minimum principle of the heat equation (i.e. that the maximum/minimum occurs at the ...
9
votes
1answer
382 views
Solving a system with a small rank diagonal update
Suppose I have the original large, sparse linear system: $A\textbf{x}_0=\textbf{b}_0$. Now, I do not have $A^{-1}$ as A is too large to factor or any sort of decomposition of $A$, but assume that I ...
9
votes
1answer
600 views
Matrix Balancing Algorithm
I have been writing a control system toolbox from scratch and purely in Python3 (shameless plug : harold ). From my past research, I have always complaints about ...
9
votes
1answer
2k views
Schrodinger equation with periodic boundary conditions
I have a couple of questions regarding the following:
I am trying to solve the Schrodinger equation in 1D using the crank nicolson discretization followed by inverting the resulting tridiagonal ...
9
votes
0answers
190 views
Imbalance of variables in Mixing Newton's method and Linear solver for a Non-linear system
Problem
Solving a non-linear system of equations.
The number of variables is the same as the number of equations.
When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{...
7
votes
1answer
575 views
full rank update to cholesky decomposition for multivariate normal distribution
This question is a specialization of full rank update to cholesky decomposition, to which I hope to get a more positive answer.
When calculating the minus log of the multivariate normal distribution, ...
6
votes
2answers
564 views
Applying matrix square root inverse in matrix-free regime
Let $A$ be a large symmetric positive definite matrix, and suppose that we can efficiently apply $A$ and have a fast solver to apply $A^{-1}$, but we do not have access to the matrix entries for ...
6
votes
2answers
271 views
Is it possible to ignore/discard part of a matrix when finding eigenvalues?
I have have multiple large matrices for which I need to find the largest absolute eigenvalue. I know that there is a large submatrix that does not vary. Is it possible to ignore/discard the submatrix?
...
6
votes
2answers
2k views
Sparse Incomplete Cholesky
I'm looking for an efficient, multicore, library to do incomplete cholesky (possibly modified). Many ILU code exists, but I can't find much about IC except in PETSC or Pastix. Could some of you drop ...
6
votes
1answer
1k views
generalized eigenvalue problem
I need to solve a real generalized eigenvalue problem
$Ax= \lambda Bx(*)$
A and B are calculated from equations below:
$$A=\sum_{i,j=1}^{N}W_{ij}(K_{i}-K_{j})\beta\beta^{T}(K_{i}-K_{j})^{T}$$
$$B=\...
6
votes
1answer
627 views
Estimate extreme eigenvalues with CG
CG may be used to estimate the extremal eigenvalues of a SPD matrix (by computing eigenvalues of tridiagonal matrix associated with the Lanczos algorithm). After a few iterations the largest ...
6
votes
1answer
378 views
Caveats of Hessian free method
Hessian free iterative optimization techniques like Newton-CG, do not explicitly compute the Hessian but instead approximate the product of the Hessian with a vector through finite difference. The ...
6
votes
3answers
2k views
Efficient eigen-decomposition of covariance matrix
I am looking for an C/C++/Python algorithm implementation that calculates eigenvalues and eigenvectors of a symmetric, positive semidefinite covariance matrix.
A general-purpose eigen-decomposition ...
6
votes
1answer
790 views
Inverse iteration to find the null singular vector of a rank-deficient matrix
I have an $n \times n$ unsymmetric matrix $A$ that results from the discretization of an ill-posed Poisson problem, and thus is rank-deficient with null space of dimension one. I want to compute just ...
6
votes
1answer
206 views
Does mean removal increase accuracy of numerical differentiation?
I wish to compute the derivative of a vector through numerical differentiation. Let's say, we use a standard 2nd order central difference scheme, to arrive at a differentiation matrix, and apply it on ...
6
votes
3answers
490 views
How to solve a small least-squares problem
This question is not very deep. Suppose I have a small rectangular matrix $A$, with number of rows and columns between $50$-$100$, respectively.
Given a right-hand side $b$, I want to solve the least-...
5
votes
1answer
189 views
Symmetric matrix which satisfies conditions of the form $v_i^T X v_i = 0$
I want to solve an underdetermined system of linear equations $A x = b$ with $A \in \mathbb{R}^{n \times r^2}, x \in \mathbb{R}^{r^2}, b \in \mathbb{R}^n$. The matrix $A$ has the following additional ...
