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 [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.

2
votes
0answers
50 views

Under what circumstances does Elemental's distributed SVD not work? [closed]

I am playing around with Elemental's distributed singular value decomposition and am running into two particular issues. Building the test at tests/lapack_like/SVD.cpp, and running with ...
1
vote
1answer
161 views

Appropriate Lapack/MKL routines to efficiently compute C = A* inv(B)

I know that, from numerical point of view, computing Ax = b B=inv(A), x= B*b are completely different things, and we should factor the matrix using TRF routine ...
11
votes
2answers
850 views

Compute all eigenvalues of a very big and very sparse adjacency matrix

I have two graphs with nearly n~100000 nodes each. In both graphs, each node is connected to exactly 3 other nodes so the adjacency matrix is symmetric and very sparse. The hard part is I need all ...
2
votes
1answer
58 views

Doubt regarding principled approach towards approximating the Hessian

In my optimization problem, the hessian has a structure such that it can be written as the sum of two matrices. Populating the first of the matrices is efficient. Populating the second one is ...
1
vote
0answers
60 views

What's the optimal method to solve for the top eigenvectors of a very large, real, symmetric matrix of limited rank?

Consider a real symmetric matrix of dimension N~10^5 and rank m~2000. What is the most efficient algorithm for determining the top m eigenvectors? If the answer isn't obvious, are there existing ...
9
votes
1answer
477 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 ...
7
votes
1answer
364 views

Efficient algorithm for solving linear system with symmetric near-tridiagonal matrix?

I would like to solve the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$, with $$\mathbf{A}=\mathbf{T}+\mathbf{C}$$ where $\mathbf{T}$ is a symmetric tridiagonal matrix and $\mathbf{C}$ is a corner-...
2
votes
2answers
558 views

Compute all eigenvectors and eigenvalues of small symmetric matrices

My problem is to compute eigenvectors and eigenvalues of a lot of small (n < 30) symetric, positive definite matrices. So far I am using LAPACK's DSYEV. The priority is speed more than accuracy. ...
7
votes
1answer
148 views

Tikhonov (Ridge) Regression and Normalization

For a typical Ridge Regression method for solving an inverse problem $$ \min_x ||A~x - b||^2 + \lambda^2||\Gamma~x||^2 $$ Which has an analytical solution of $$ \hat{x}_{est}=(A^TA+\lambda^2 \Gamma^T\...
1
vote
0answers
55 views

bound error for iterative method for solving linear system

$A$ is square and positive definite, and let $r_k = Ax_k - b$. Also let $M = \frac{1}{2}(A+A^T)$. I want to show that $$\frac{||r_{k+1}||_2}{||r_k||_2} \le \left(1-\frac{\lambda_\min(M)^2}{\lambda_\...
3
votes
1answer
92 views

linear programming feasiblity checking

Is there any sufficient and necessary condition to check the feasibility of the linear constraints $Ax=b, x\geq 0$ without solving an LP with a constant objective function? $x$ is the variable and $...
0
votes
1answer
71 views

Efficiently approximating sum of 2-norms

Suppose I have a real vector $\bf x$ of length $KN$, where $K<<N$. Let's say I break this vector $\bf x$ up into $N$ vectors each of length $K$, $${\bf x}_1,...{\bf x}_n.$$ Now I would like ...
1
vote
0answers
58 views

Efficiently computing the properties of a Chebyshev series

Suppose we have some function $f(x)$ defined as a Chebyshev series up to order $M$: $$ f(x) = \sum_{n=0}^{M} c_n T_n(x). $$ For a given coefficients vector $\mathbf{c}$, and $x \in [-1,1]$ I'm ...
1
vote
0answers
82 views

How to get the eigenvalues of Hamiltonian in an over complete basis

Let $|\psi_i\rangle$, $i=1...N+m$, be a set of overcomplete basis vector in a $N$-dim Hilbert space. The following are known: (Einstein's summation convention assumed) $$\hat{H}|\psi_i\rangle=H_{ji}|\...
1
vote
1answer
584 views

Eigen - Solving Complex Generalized Eigenvalue Problem

I've been using the Eigen C++ linear algebra library to solve various eigenvalue problems with complex matrices. I've recently had to use a generalized eigenvalue solution process, only to be ...
1
vote
0answers
109 views

Updating factorization of Laplacian (add/remove edges)

For a graph $G=(V,E)$, recall that the unweighted Laplacian is $L:=D^\top D$, where $D\in\{-1,0,1\}^{|E|\times|V|}$ is the graph "gradient" operator that subtracts adjacent vertex values onto edges. ...
2
votes
1answer
88 views

Solving system of related equations without completely recomputing LU decomposition for each equation

Let $\Sigma$ be positive definite and the $D_i$ positive diagonal. Let the $X_i$ be unknown square matrices. Consider the system of equations: $$(I+\Sigma D_i)X_i=\Sigma\hspace{5mm}\text{for}\...
8
votes
1answer
187 views

Solving two inverse problems with same solution

I've got two inverse problems, $$A_1 ~ x = b_1 \qquad A_2 ~ x = b_2$$ So far I've been solving them independently using Tikhonov Regularization and getting two estimates for $x$. However in my case $...
2
votes
1answer
323 views

Rectangular Cholesky Decomposition

Assume we have a positive semidefinite matrix $A$ with $A\in\mathbb{R^{n\times n}}$. Clearly a cholesky decomposition $A=B^TB$ exist with $B\in\mathbb{R^{n\times n}}$. For my research it would be ...
0
votes
1answer
169 views

Open Source Linear Algebra Library

I am making a code in C that requires the equivalent of Matlab's '\' command for a linear system of the form AX=B where A is an NxN matrix and X, B are Nx1 vectors- i.e a code that performs X=A\B that ...
3
votes
2answers
434 views

Python environments for AMG and Gauss Seidel as solvers instead of preconditioners

I am working on block preconditioning and seemingly it is common to write customised Krylov solvers for them. Within each solver, the individual block linear system with preconditioners are ...
3
votes
0answers
96 views

Eigenvalue decomposition of the sum: $AA^T$ + diag($u$)

Suppose $A\in\mathbb{R}^{n\times c}$,$u\in\mathbb{R}^n$,$n\gg c$. The time complexity of eigenvalue decomposing directly for matrix $AA^T+\text{diag}(u)$ is $O(n^3)$. And it is easy to avoid $O(n^3)$ ...
1
vote
0answers
29 views

Difference between Chebyshev first and second degree iterative methods

Consider linear equation $Au = f$. We want to solve it with iterative method (assuming $A$ is good). First order iterative method is: $$ u^{k+1} = u^k - \alpha_{k+1}(Au^k - f), $$ The second degree ...
7
votes
2answers
126 views

Lanczos algorithms for Hermitian system with Toeplitz kernel

Basically, I am trying to compute the SVD of a large Hermitian matrix $H$ using Lanczos iteration, while $H$ consists if a Toeplitz kernel $K$, which should be able to help speed up the matrix-vector ...
4
votes
3answers
1k views

Understanding Finite-Element Modal Analysis

I am teaching a basic course on computational physics and for the last part of the course I will introduce freshman physics undergraduates to finite-element modelling methods. I am preparing a COMSOL ...
1
vote
1answer
123 views

How to determine the truncation error with products and quotients

If I have an equation given by $$\displaystyle Y = \frac{a^2}{d^2}\frac{(1-c^2\frac{c}{a})}{(1-b^2)}$$ and I expand $a,b,c,d$ in a Taylor series, where $a$ is truncated at the $A^{th}$ order, $b$ is ...
5
votes
0answers
122 views

Rank-one Update to a Rank Revealing QR (RRQR) Factorization?

Suppose we are given an RRQR factorization for some matrix $A \in \mathbb{R}^{m \times n}$, $A\Pi = QR$ where $m > n$. Is there a cheap way to update $A' = A + uv^{\top}$ given this factorization?...
4
votes
3answers
165 views

Eigenvectors of Black-box matrix

$\DeclareMathOperator{\diag}{diag}$ Consider the generalized eigenproblem $A\mathbf{x}=\lambda B\mathbf{x}$. When solving PDEs numerically (specifically, I am interested on finding the Dirichlet ...
3
votes
2answers
486 views

Zero Eigenvalues in Lanczos Algorithm

I need to find the smallest few eigenvalues of a Hamiltonian (exact diagonalization) I use Python, and SciPy's built-in sparse eigenvalue solver. I notice, however, that for my small system (only a ...
0
votes
1answer
66 views

Show the symmetric Gauss-Seidel converges for any $x_0$

Let $A\in\mathbb{R}^{n\times n}$ is symmetric positive definite and consider solving linear system $Ax = b$. Show that the symmetric Gauss-Seidel iteration converges for any $x_0$. Solution - Since $...
0
votes
1answer
74 views

Linear stationary iteration method

Suppose you are attempting to solve $Ax = b$ using linear stationary iteration method defined by $$x_k = G x_{k-1} + f$$ that is consistent with $Ax = b$, i.e., for which $f = (I - G)A^{-1}b$. Suppose ...
3
votes
1answer
175 views

Efficient algorithm for a matrix product

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
3
votes
1answer
208 views

Determine a sufficient condition for a Hessenberg matrix to be nonsingular

Consider $A\in\mathbb{R}^{n\times n}$ whose nonzero elements are restricted to the main diagonal the strict upper triangular part, and the first subdiagonal. For $n = 8$ the locations that must be ...
0
votes
1answer
78 views

$LU$ Factorization of a nonsingular matrix with a particular pattern

Consider $S\in\mathbb{R}^{n\times n}$ whose nonzero elements have the following pattern for $n = 8$: $$\begin{pmatrix} 1 & 0 & 0 & 0 & \mu_1 & 0 & 0 & 0\\ 0 & 1 &...
2
votes
1answer
158 views

Schur complement of a matrix $A$

Let $A\in\mathbb{R}^{n\times n}$ and its inverse be partitioned $$A = \begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22}\\ \end{pmatrix},\:\: A^{-1} = \begin{pmatrix} \tilde{A_{11}} & \...
1
vote
1answer
361 views

Preconditioning of two step iteration for dense matrices

I would like to solve a dense linear system the form in python $$ L\left(\boldsymbol{x}\right):=\left[\gamma^+\left[\boldsymbol{A}+\frac{1}{2}\boldsymbol{B}^{-1}\right] +\gamma^-\left[\boldsymbol{A}-\...
0
votes
1answer
156 views

Parallel linear algebra without OpenMP

I have searched through the archives without success. Apparently, the question is simple: What linear algebra library can I use that is parallel (shared memory) but without OpenMP? As far as I've ...
2
votes
0answers
46 views

Optimal ordering in Jacobi SVD algorithm

In Jacobi SVD algorithm as given here every pair of columns of the matrix is orthogonalized until convergence. I want to know that how does the order of selection of the pair of columns affect the ...
6
votes
1answer
156 views

Is there an eigenvalue estimation method more accurate than Gershgorin's, which uses no multiplication?

Suppose I have a real symmetric matrix. I would like to tell wether it has at least $k$ strictly positive eigenvalues, but using only additions (no multiplications). Is there a method that I could use?...
1
vote
1answer
97 views

Numerical method for solving a system with positive definite blocks

I have a system with below coefficient matrix $$ C = \begin{pmatrix} A & B^T \\ B & D \end{pmatrix},$$ where, $A$ and $D$ are square and positive definite. Furthermore, if $B$ be square, ...
3
votes
2answers
1k views

A numerical GMRES example

I'm having trouble understanding how GMRES works. I've read the part in Saad's book and a few others but still I am confused. Can someone provide me a numerical example to understand it better? Or if ...
5
votes
1answer
131 views

Solve for $C$ such that $C^{T}AC$ is banded of given width

Given a symmetric matrix $A$, the Lanczos algorithm outputs $C$ such that $C^{T}AC$ is tridiagonal. Is there a generalization of this such that $C^{T}AC$ is banded of specific width $w$? Note that $C$...
5
votes
0answers
270 views

Compute sparsity pattern of $A^2$

Suppose we have a sparse matrix $A$. Is there any way to compute just the sparsity pattern of $A^2 = A \cdot A$ (I do not actually need to know what exactly the nonzero value are) faster than to ...
6
votes
1answer
232 views

Robust smoothers for geometric multigrid

I'm searching for robust smoothers for geometric multigrids. By robust I mean: Effective for high order approximations (say spectral element, spectral Discontinuous Galerkin), Parallel (suitable for ...
2
votes
0answers
359 views

Fixing a near singular covariance matrix

Given a near singular covariance matrix, the standard method of 'fixing' it seems to be to add a small damping coefficient $c>0$ to the diagonal, which serves to bump all the eigenvalues up by this ...
0
votes
2answers
43 views

Grouping Boolean vectors by similarity up to a rotation [duplicate]

I'm looking for an algorithm to take the entire vector space of length n Boolean vectors and partition it into vectors that are the same up to a rotation of the entries. For example if n=3 the ...
6
votes
2answers
258 views

Solving $A=B+AB$ without matrix inverse

I have a linear system of equations that can be expressed $$A=B+AB,$$ where $A$ and $B$ are real, symmetric matrices. I would like to solve for $A$ given $B$. At present, I solve for $A$ directly via $...
0
votes
1answer
75 views

Most efficient way to compute eigenvectors / values of this matrix?

I have a symmetric $ 3 \times 3 $ matrix $A$ and I need to compute the eigenvectors and eigenvalues of this. I know that I can use something like Lapack, but I also know that this can be computed ...
2
votes
1answer
191 views

Probability of reconstructing a word using c substrings from a random sample

Consider a voice recording split into it's phonemes as our sample $S=(s_1,...,s_k) \in \Omega = P^k$. The number of phonemes is $|P| = 40$. Then I have a word $w = (w_1,...,w_n) \in P^n$. I want to ...
1
vote
1answer
274 views

Solving a linear system whose matrix has imbalanced diagonal entries

I am trying to solve following set of equations: A(i,i-2)*u(i-2) + A(i,i-1)*u(i-1) + (A(i,i)+β(i) )*u(i) + A(i,i+1)*u(i+1) + A(i,i+2)*u(i+2)= B(i) + β(i) where i=1:1000000 If values of β varies(...