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

1,124 questions
Filter by
Sorted by
Tagged with
119 views

### Rank-1 correction of matrix exponential

I need to approximate the following in $O(d)$ time for $d\times d$ diagonal $A$ and rank-1 $B$ $$u^T \exp(-A+B) v$$ Here $u,v$ are vectors in $\mathbb{R^+}^d$, $A,B$ are positive semi-definite and $B$ ...
• 2,273
102 views

### Schur complement formulation of linear system

Consider a system of the following form: $$(A+K)x=b$$ where $A$ is symmetric, positive definite and block diagonal (in fact, a block diagonal matrix made of stiffness matrices arising from FEM ...
• 157
206 views

### How to optimize an approximated matrix multiplication?

[UPDATING] The old one is a simplified version of the current one. Here is a solution based on the answer proposed by professor Bangerth down below. To describe what I am trying to do, first rewrite ...
1 vote
83 views

### Powers of convergent DPR1 matrices in $O(d)$ time?

Suppose $u$,$v$ are vectors and $A$ is a convergent $d\times d$ diagonal + rank-1 matrix. How do I estimate $u^T A^k v$ in $O(d)$ time? Powers of convergent diagonal $D$ can be computed in $O(d)$ time ...
• 2,273
232 views

### Faster than forward substitution?

I have a matrix of the form: $M:=\begin{pmatrix} S_1 & & & \\\ Q_1 & S_2 & & \\\ & ... & ... & \\\ & & Q_n & S_n\end{pmatrix}$ where the blocks ...
• 157
71 views

### Approximating eigenvalues of DPR1 matrix with special properties

In my application, I have a sum of diagonal $A$ and rank-1 $B$ $$T=\underbrace{\text{diag}(1-2\alpha h+2\alpha^2 h^2)}_A + \underbrace{\alpha^2 hh^T}_B$$ Where $h$ is a vector $\in \mathbb{R}^d$ with ...
• 2,273
352 views

### Computing powers of diagonal + rank-1 matrix?

I'm using a numeric root-finder to find $k$ satisfying $\|A^k x\|=c$ where $A$ is a symmetric $d\times d$ diagonal + rank-1 matrix. How to compute $A^k x$ efficiently? For integer $k$, I can get the ...
• 2,273
58 views

### Eigenvalues of same operator expressed in two different orthonormal basis are coming out different

I have an operator $H$. I express $H$ as a matrix in the orthonormalized $\{ |e > \}$ basis. Then I diagonalize it to obtain eigenvalues, let's say for example $H$ is $6 \times 6$ and the ...
101 views

### Ways to fix block Lanczos tridiagonalisation numerical instability for matrix with degenerate, closely spaced eigenvalues?

I want to run a block Lanczos block-tridiagonalization on a hermitian, sparse matrix (of relatively small size $\sim 10^2 \times 10^2$). However the matrix typically has many eigenvalues that are ...
• 21
1 vote
158 views

### Lanczos memory complexity for dense matrices

Does the Lanczos algorithm remain memory efficient even if the original Hermitian matrix is dense?
1 vote
62 views

### Does the choice of a complex inner product affect Krylov methods?

As far as I understand there are two definitions of the complex inner product: $$(a,b) = b^H a$$ and $$(a,b) = a^H b$$ I know some linear algebra libraries such as BLAS and Eigen uses the second one. ...
1 vote
43 views

### FEM Basis for functions of two variables in $\mathbb{R}^2$ (Applied to Linear Full Stokes Equations)

I'm trying to do FEM for a very basic version of the linear full Stokes equations in two dimensions. Say we are working in the grid $[0,1]\times[0,1]$ in the $xy-$plane. To solve an FEM problem for a ...
• 111
215 views

### Inverse power iteration and solving singular system

The algorithm for the inverse power iteration works as following : \begin{align} &v^{(0)} =\text{ some vector with }\|v^{(0)}\|=1\\ &\text{for }k = 1, 2, \ldots\\ &\qquad\text{Solve } (A - ...
• 169
77 views

### Householder Vector algorithm in Golub and Van Loan

(This is repost of a question first asked on Mathematics. Hopefully there are more people here who have a copy of Golub and Van Loan to hand) In the 4th edition of "Matrix Computations", ...
216 views

### How can I express the solution to a discrete Lyapunov equation as an eigenvalue problem?

Given the discrete Lyapunov equation $$AXA^T - X + Q = 0$$ how can I solve for $X$ as a function of the eigenvectors of some matrix $H$? More precisely, in the case of the continuous Lyapunov equation ...
• 165
112 views

### Starting point to use Trilinos linear algebra packages?

I have experience with classical linear algebra packages in C++ like Eigen, Blaze, etc. I have never wrote my own PetSC back-end solver but I used/modified several of them. In a new project I would ...
1 vote
108 views

### What's the best modern algorithm for recursive least squares?

Recursive least squares can be implemented using the Sherman–Morrison formula to avoid resolving, however, have better methods without $n^2$ cost been developed? I'm interested if there is a good ...
• 111
104 views

• 227
92 views

### How to estimate stability and stiffness of a system of coupled ODEs?

I'm running into issues with Python/Julia ODE solvers requiring prohibitively small timesteps to evolve a system of 4 coupled ODEs (the order of magnitude of the state variables and time unit span ~40-...
• 193
118 views

### Largest singular value without using the adjoint

The square of the largest singular value of a linear map $A$ can be computed by using the power iteration for $A^TA$ and one advantage of this is that the iteration is matrix free, i.e. you only need ...
• 1,738
1 vote
295 views

### Calculate average distance between pairs of points without computing full distance matrix

Suppose I have a set of $N$ points of shape $N \times D$, where $D$ is the dimensionality. I want to compute the average Euclidean distance between all points, as well as additional moments such as ...
• 165
109 views

### Finding the correct order of eigenvectors of a parameter-dependent Hermitian matrix

so, I have a symmetric, analytic matrix $\mathbf{H}(x)$ ($x$ is real). Because $\mathbf{H}(x)$ is analytic and $x$ is real, it is possible to find analytic functions for the eigenvectors and the ...
• 153
44 views

### Finding matrix of a linear transformation using R programing

The full question is: Let {u1, u2,···, un} and {x1, x2,···, xm} be bases for Rn and Rm respectively. Let T:Rn→Rm be the linear transformation whose associated matrix with respect to the above bases is ...
140 views

### Numerical diagonalization of Hamiltonian

Framework I am trying to diagonalize the Bogoliubov-de Gennes Hamiltonian. The problem is that the Hamiltonian contains a Laplacian. This could be solved by using a discretized Laplacian. How I tried ...
• 21
70 views

### Requesting for Finite Difference Methods reference in Portuguese or English

Crossposted on Mathematics SE I have been assigned a group project for an introductory Linear Algebra subject on Finite Difference Methods and sparse matrices. Our professor advised we use Gilbert ...
• 33
45 views

### Solving linear system and obtaining operator norm

I need to solve a linear system of the form $(\mathrm{Id} + \mathbf{J})\mathbf{x} = \mathbf{b}$ for $\mathbf{x}$ and I also need to compute the operator norm of $\mathbf{J}$ (i.e. the largest singular ...
• 183
1 vote
100 views

### Fast algorithm to compute chi-square

I would like to evaluate the chi-square of the form $\chi^2=v^{T}C^{-1}v$ where $v$ is a column vector and $C$ is a covariance matrix. Both $v$ and $C$ are known and $C$ is a $740\times740$ matrix. ...
• 123
I have a linear system of the type $A x = y$ where A is a dense, square, symmetric, positive definite matrix, $x$ a vector of unknown parameters, and $y$ is a vector of observed quantity. I know that ...