# Tagged Questions

Questions on the algorithmic/computational aspects of linear algebra, including the solution of linear systems, least squares problems, eigenproblems, and other such matters.

51 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 ...
46 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 ...
65 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)$ ...
23 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 ...
35 views

### Lanczos algorithms for Hermitian system with toeplitz kernel

Basically I am trying to compute the SVD of a large hermian matrix H using Lanczos iteration, while H consists if a toeplitz kernel K, which should be able to help speed up the matrix-vector ...
116 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 ...
36 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 ...
28 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? ...
72 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 ...
131 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 ...
40 views

57 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 ...
50 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 ...
97 views

### Numerical Solution of Matrix with Diagonal Elements of Highly Varying Order

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(...
43 views

26 views

### SPECT reconstrction using MLEM

In Single-Photon Emission Computerized Tomography (SPECT) parallel beam reconstruction using Maximum-Likelihood Expectation–Maximization(MLEM), is it sufficient to scan the object around 180 degree? ...
20 views

### Ordering of eigenvectors to maximise trace of diagonalising matrix

I asked a similar question on the Mathematics stack exchange here without much success, so I thought I'd ask it with a more practical bent here. Suppose we have a Hermitian matrix $H$ with (for the ...
55 views

### Preconditioned Steepest Descent

For my program assignment I need to write a preconditioned steepest descent algorithm. I have psedo-code from my professor which is here: From reading in my text on this method they say that $P$ is ...
63 views

### Methods for solving rectangular, full-rank systems of equations — which is best?

Suppose I have a large, sparse, $m \times n$ matrix $A$, with $m \gt n$ and $\text{rank}(A) = n$. I wish to solve $Ax=b$. Suppose I know that $A$ has the following characteristics: $A$ is somewhat ...
36 views

How do I solve for the object distance to each receiver for three radar receivers on the ground, each the same distance from the other, and each receiving echoes, reflected from an object overhead, of ...
64 views

### Algorithm to decompose a sparse unitary matrix into a Kronecker product of smaller unitary matricies

Given some sparse unitary square matrix $A$ ($dim=2^n$ if it matters), is there an algorithm to decompose $A$ into a Kronecker/tensor product of smaller unitary matrices? In other words: decompose ...
112 views

### Power Iteration over Rayleigh Quotient Iteration?

It is a commonly known fact that the Rayleigh Quotient converges cubically (1), while the Power Iteration may converge slowly if the difference between the dominant and second-dominant eigenvalue is ...
146 views

### What is the state of the art algorithm for diagonalizing real symmetric matrices?

There are many methods for diagonalizing matrices, probably the most widely used is the combination of Householder transformations and the QR algorithm. Is there any superior method for diagonalizing ...