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

learn more… | top users | synonyms

4
votes
0answers
87 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 ...
1
vote
0answers
35 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
0answers
18 views

Algorithm to group Boolean functions by rotation similarity

I'm looking for a way 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 partitions ...
0
votes
2answers
19 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
148 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 ...
-3
votes
0answers
25 views

MCNPX simulation [closed]

I want to ask about neutron source in input file. The problem is I have subcritical core, fuel is mixed between thorium and uranium 50 % and I need to put 2 neutron sources in different places ...
0
votes
1answer
49 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 ...
0
votes
1answer
23 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 ...
0
votes
1answer
48 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 β ...
3
votes
0answers
35 views

Quasi Newton method for block diagonal Hessian

I am having an unconstrained optimization problem, where the Hessian is positive semidefinite and block diagonal. The function is strictly convex, hence, the curvature condition ($ s^{T}_{k}y_{k} > ...
1
vote
1answer
65 views

Efficiently rotate vector in 2D (and 3D)

I need to efficiently rotate a 2D (and 3D) vector in a CUDA kernel. I was thinking about generating random unitary rotation matrices. I don't need to know the angle, it just has to be randomly ...
5
votes
0answers
75 views

Galerkin FEM error when using even number of elements

Intro: I am developing a Galerkin FEM code in matlab - starting small with a simple 1D ODE. The equation I'm trying to solve is: $$a u_x = cos(x), x \in [0, 2\pi]$$ Which has a known exact solution ...
0
votes
0answers
41 views

One parameter family of linear systems

Suppose $A\in\mathbb{R}^{n\times n}$ is dense and $D\in\mathbb{R}^{n\times n}$ is a diagonal and nonnegative. Given a fixed vector $b\in\mathbb{R}^n$, define the following function ...
2
votes
0answers
23 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? ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
61 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 ...
0
votes
0answers
36 views

how to solve distance from overhead object to each of 3 ground-based radar receivers

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 ...
4
votes
1answer
56 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 ...
4
votes
1answer
100 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 ...
8
votes
1answer
139 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 ...
0
votes
0answers
99 views

Preconditioned Conjugate Gradient linear system solver in MATLAB

I have been trying to use the MATLAB's pcg() function to minimize an energy functional. Converting minimization problems to the solution of a linear system is ...
4
votes
1answer
99 views

Efficient way to generate a list of possible matrices (all integer components) with a determinant $V$

I have an interesting problem from my research that I have been struggling to solve. One part of the problem involves generating all possible matrices, where each set contains three integer vectors, ...
0
votes
1answer
103 views

Fast computation of square root inverse of matrix, matrix being determined from Ax=b form

I have an equation of the form $J^Te=f$, where $e$ and $f$ are known vectors and $J$ is an unknown matrix. How can I efficiently compute $J^T(JJ^T)^{-1/2}e$ ? My motivation to address this problem ...
1
vote
1answer
49 views

Calculate inverse of dense matrix with entries of very different magnitude

I need to calculate the inverse of a dense matrix, with some elements taking values as high as 1e9 and some around 1e2. What would be the best method to do it? Note: I am more concerned about the ...
0
votes
1answer
73 views

Is there any rapid way to calculate the determinant of NXN covariance matrix?

I searched the web and found some C code for calculating the determinant of a $n\times n$ matrix. This code however seems timing complexity, and run pretty slow especially when handling a larger ...
4
votes
0answers
71 views

Conjugate gradient: the 1-norm of the residual

I am trying to solve $Ax=b$ using the conjugate gradient method. However, it is important to me to obtain a bound not only on the usual residual $||b-Ax_k||_2$ but also on the quantity $||b-Ax_k||_1$. ...
3
votes
1answer
98 views

strassen algorithm vs. standard multiplication for matrices

I am trying to figure out at exactly what dimension it is better to use Strassen algorithm rather than the standard multiplication. I know that there is 18 addition and subtraction in Strassen ...
3
votes
3answers
101 views

How to assemble Global matrix (for coupled) problem?

I'm trying to assemble global matrices for the following system. $$ \begin{bmatrix} K& Q\\ Q^T&S \end{bmatrix} \begin{bmatrix} u_h\\ p_h \end{bmatrix} = \begin{bmatrix} f_u\\ f_p ...
-1
votes
2answers
187 views

$LU$ factorization

Our task is to implement a factorization routine that given A in a suitably efficient data structure returns the factors $L$ and $U$ where $L$ is unit lower triangular and $U$ is upper triangular. In ...
3
votes
1answer
78 views

Resources for solving mixed left and right matrix equations

I'm looking to solve a matrix equation and not sure where to start looking for resources. The equation is $$AX + XB = C\,,$$ where $A\in\mathbb{R}^{n\times n}$, $B\in\mathbb{R}^{m\times m}$, ...
4
votes
1answer
39 views

Find a consistent cyclic orientation on a conic section

I have a conic section in the real projective plane. This is represented by its real symmetric 3×3 matrix. I verify that the conic section is real and non-degenerate by computing the eigenvalues of ...
3
votes
0answers
56 views

Does there exist a Fourier transform algorithm for perturbed data?

Assuming I have a length-$n$ real vector $x$ and have already computed its Fourier transform $\hat x$ (in time $O(n\log n)$), I would like to compute the Fourier transform of $y = x + \delta x$, where ...
2
votes
3answers
81 views

Angle of rotation at a point in a deformed triangle

I have a 2D triangle which deforms with each vertex moving by some small ($\sin(x) \approx \tan(x) \approx x$) displacement vector. The displacement of any point in the triangle is linearly ...
4
votes
0answers
35 views

Pseudoinverse of perturbed matrix

How does the pseudo inverse of a full column rank matrix change if I rescale a single row? In more detail the problem is the following: We have a fixed matrix $V$ with linear independent columns and ...
3
votes
1answer
75 views

Condition number of $X^{T}AX$

$A$ is a symmetric matrix and is known to be invertible. $X$ is rectangular of size $(N+p) \times N$ with $p > 0$ but full column rank. Can we provide an upper bound on the condition number of ...
0
votes
0answers
34 views

Constrained SVD/Lanczos given left/right matrices are banded

$A$ is a symmetric (known to be invertible) matrix of size $(N+p) \times (N+p)$ and $X$ is a rectangular matrix of size $(N+p) \times N$. The product $X^{T}AX$ is well-defined and non-singular. One ...
1
vote
0answers
55 views

Computing eigenvectors from the QR algorithm

I've seen a few other posts on this topic but none have full answers. I'm trying to implement some eigen-decomposition algorithms. I've managed to get the Explicit QR algorithm and the Implicit ...
0
votes
1answer
68 views

Extending the Frobenius inner product to all matrix inner products

So in ${\bf R}^{n\times p}$ we have the Frobenius inner product given by $$\langle A, B\rangle=\text{tr}(A^TB)$$ which can be interpreted as the Euclidean inner product on ${\bf R}^{np}$. My ...
0
votes
0answers
32 views

Unitary matrix representing Discrete Fourier Transform

Let $F_n\in\mathbb{C}^{n\times n}$ be the unitary matrix representing the discrete Fourier transform of length $n$ and so $F_n^{H}\in\mathbb{C}^{n\times n}$ is the inverse DFT of length $n$. For ...
3
votes
2answers
139 views

Are the Finite Difference and Finite Volume Methods different after the application of the Gauss Divergence theorem on the FVM?

I have a rudimentary question about the differences between finite difference (FDM) and finite volume methods (FVM). In FDM we concentrate on the nodes (points) in space while in FVM we concentrate ...
3
votes
1answer
185 views

What category is this problem?

My first question, please excuse me if its too basic. I have a matrix of evenly spaced geographical points; say 10 x 10, which I will call seed points. Each seed ...
1
vote
0answers
44 views

Reorder eigenvalues in QZ factorization in Python-Scipy /Matlab [closed]

Python and Scipy seem capable of replicating the QZ factorization of Matlab when the option "complex" is used in the command scipy.scipy.linalg.qz Yet, it seems that is still not possible to obtain ...
10
votes
1answer
262 views

Smallest eigenvalue without inverse

Suppose $A\in\mathbb{R}^{n\times n}$ is a symmetric, positive definite matrix. $A$ is big enough that it's expensive to solve $Ax=b$ directly. Is there an iterative algorithm for finding the ...
5
votes
1answer
72 views

Numerical computation of Perron-Frobenius eigenvector

I would like to efficiently and (to the extent possible) reliably find the Perron-Frobenius eigenvector of non-negative matrices. These are not stochastic matrices, they are typically dense, and their ...
3
votes
1answer
68 views

Calculating left eigenvector when I know the right eigenvector

I'm using power iteration to find the dominant right eigenvector of some large-ish matrices ($1000\times 1000$ to $10000\times 10000$ or so, maybe I'll need to go bigger later) with non-negative ...
6
votes
1answer
44 views

Finding all binary vectors with given A-length

I am given a $n \times n$ matrix $A$ with real entries and define the inner product $$\langle x,y\rangle = x^T A y.$$ I am also given an integer $k$ and need to find all binary vectors $x$ such that ...
5
votes
1answer
59 views

Code to update dense QR and Cholesky factorizations

I am looking for some production-ready code to update dense QR and/or Cholesky factorizations (by adding / removing rows and columns or making small-rank updates -- yes, I need all these cases). I ...
4
votes
2answers
96 views

Advice on handling many “small” matrices in parallel

I'm working on a small fun project on the side for a numerical method I've been working a bit with. Roughly, the computational problem I have to solve is the following: Assume you have a collection of ...
11
votes
2answers
175 views

Algebraic Multigrid: Why does the product of interpolation and restriction not result in something with norm 1?

I'm currently working with "A Multigrid Tutorial" by Briggs et al, Chapter 8. The construction of the interpolation operator is given as: Then construction of restriction operator and fine grid ...