Stack Exchange Network

Stack Exchange network consists of 174 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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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

1
vote
1answer
37 views

Calculate partial trace of an outer product in Python?

I have a python implementation of calculating the partial trace over select dimensions. ...
3
votes
1answer
70 views

Level scheduling of triangular sparse matrices

Assume one has a triangular sparse matrix and want to solve $Lx=b$ where $b$ and $L$ are known. This can be done easily by using forward substitution when $L$ is a lower triangular matrix. Forward ...
2
votes
1answer
110 views

Can the Power Method be used here?

Given a set of $n$ points on which a triangulation is performed, it is possible to construct coefficients $\lambda_{ij}>0$ such that each point $x_i$ is a convex combination of the points connected ...
2
votes
0answers
58 views

Simultaneous update to barycenters

Suppose a tiling is given in 2D (an embedding of a planar triangulated graph), with all faces convex. Now suppose one moves each point, one by one, to the barycenter of its neighbors. I think that ...
0
votes
0answers
37 views

Finding attribution of coefficient in a matrix

I have the following $d*n$ matrix in $\{0, 1\}$ \begin{bmatrix} x_{11} & x_{12} & x_{13} & \dots & x_{1n} \\ x_{21} & x_{22} & x_{23} & \dots & x_{2n} \\ ...
4
votes
2answers
108 views

How “sparse” should a sparse matrix be to see benefits?

I have a matrix, whose size scales as $2^N$ (assume even $N$). In each row of the matrix, only about $2^{N/2}$ of the entries are filled ($N$ can be somewhere between 10 and 40, depending on what's ...
3
votes
0answers
68 views

Unstable convergence of a Poisson equation

What could be the reason that the solution of a Poisson equation is smooth when obtained by an iterative solver, only if the maximum residual is set to a high value (e.g. 0.1)? When the maximum ...
8
votes
1answer
143 views

Computing geodesic distances with diffusion

I am trying to solve an APSP (All-Pair Shortest Path) problem on a weighted graph. This graph is actually a 1, 2 or 3 dimensional grid, and the weights on each edge represent the distance between its ...
5
votes
1answer
114 views

Generate approximately semi-orthogonal tall matrix approximately satisfying constraints

I have a set of matrices $\{(A_i,D_i)\}$ for $i\in\{1,\ldots,n\}$, where: Each $D_j\in\mathbb{R}^{S\times S}$ is diagonal, and every entry on the main diagonal is non-negative. Each $A_j\in\mathbb{R}^...
7
votes
1answer
135 views

Least Squares with Dense-Block Diagonal Structure

I need to solve a least squares problem that takes the following form: $$p = \arg \min_{x}\Vert J V x - y \Vert_2, $$ where $J \in \mathbb{R}^{N \times N}$ is a general dense matrix, and $V \in \...
4
votes
1answer
180 views

How to solve the following Frobenius norm-minimization problem?

Background We know how to solve the following minimization problem $$ \min_{X} \lVert AX - B \rVert_F^2 $$ But what about the extended version? $$ \min_{X} \lVert A \begin{bmatrix} X & X^2 \...
3
votes
1answer
103 views

Compute bilinear form with LAPACK

I need to compute a bilinear form for a set of left and right vectors $$ w_k = \sum_{i,j} V_{ik}^*A_{ij}U_{jk},$$ where $A_{ij}\in\mathbb{R}$ and $U_{jk}, V_{ik} \in \mathbb{C}$ (Assume that all the ...
4
votes
1answer
73 views

Matrix exponential of hermitian matrix with eigenvectors from generalized eigenvalue problem

I want to calculate the following expression $$ \exp(-i\Delta t\mathbf{H}) $$ where $\mathbf{H}\in\mathbb{C}^{n\times n}$ is a hermitian matrix. Since I have a highly optimized eigensolver in the code ...
0
votes
0answers
71 views

Non-linear equation solver algorithms

I currently have code that uses the biconjugate gradient stabilized (bicgstab) method to solve $Ax = b$ for $x$, where I never create the $A$ matrix explicitly, but only have a function $F(x) = Ax$ ...
6
votes
2answers
163 views

Nonlinear eigenvalue problem - MATLAB code

I'm trying to solve a nonlinear eigenvalue problem in MATLAB, still without success. It's a problem about graphene plasmonics. The nonlinear eigenvalue problem is given below: \begin{equation} \frac{...
0
votes
0answers
75 views

Using Gram-Schmidt to obtain Spherical Harmonics

If we don't know the Spherical Harmonics offhand, we could try to observe they are stratified by degree. So that $x^a y^b z^c$ will have degree $n = a+b+c$. These do not form an orthonormal basis, ...
3
votes
1answer
168 views

How to solve the inverse problem of least-squares?

Focusing on following least squares problem: $$\min\limits_{V} \lVert Z - WV \rVert _{_F}^2$$ $$Z∈{R}^{m\times n},\quad W∈{R}^{m\times k},\quad V∈{R}^{k\times n},\quad k\lt m\lt n $$ This problem ...
5
votes
1answer
42 views

Transform from linear index of a packed triangular matrix to dense indices

Given indices $i,j$ s.t. $0\leq i \leq j <n$, the function $f(i,j)=i+j(j+1)/2$ maps 2d indices to linear indices in column major order. What is the fastest way to invert this function? My first ...
7
votes
2answers
169 views

Is large condition number good measure of nearness to singularity for a matrix?

I am new to numerical linear algebra, so i came to know that condition number in 2-norm case will be ratio of largest to smallest singular value. Another concept "Nearness To Singularity" is measured ...
4
votes
1answer
113 views

How can I apply Euler's Method to predict a point in time rotating around multiple axis'

I am xposting this from my original stackoverflow question where I was presented with a coding challenge that I have been able to narrow down extensively and I think it lies with Euler's Method. Here'...
1
vote
1answer
169 views

How to use CSDP to express a semidefinite program?

I am trying to use CSDP and am struggling with it. Consider, for example, the following semidefinite program $$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & Q - A' Q A - \...
3
votes
1answer
109 views

Diagonalizing a block tridiagonal Toepliz Hermitean matrix

I have to diagonalize, within a Fortran-written code, a block tridiagonal Toeplitz Hermitian matrix, e.g. $$ \left[ \begin{array}{ccccc} \ddots & \hat{A} & & & \\ \hat{A}^\dagger &...
2
votes
2answers
54 views

Discrete-time input matrix when one of the eigenvalues of the system matrix is zero

If we have a continuous time state-equation, $$ \dot{x}(t) = A x(t) + B u(t)$$ where $A \in \mathbb{R}^{n \times n}, x \in \mathbb{R}^{n\times1}, B \in \mathbb{R}^{n \times m}, u \in \mathbb{R}^{m \...
2
votes
0answers
85 views

Efficiently solve linear system with matrix quadratic form

Take the system $$A^TCAx=b$$ where $$A\in\mathbb{R}^{n\times m},\;C\in\mathbb{R}^{n\times n},\;x,b\in\mathbb{R}^{m}, \;m\leq n$$ and $$A^TA=I$$ and $$Cy=d$$ can be solved efficiently in general (...
4
votes
2answers
454 views

Why does sparse linear algebra have a low arithmetic intensity?

I often see the terms "low arithmetic intensity" and "memory-bound" associated with sparse matrix operations. However, my intuition is that a sparse matrix operation should be less memory-bound, if ...
-1
votes
2answers
179 views

Does armadillo library slow down the execution of matrix operations?

I've converted a MATLAB code to C++ to speed it up, using the Armadillo library to handle matrix operations in C++, but surprisingly it is 10 times slower than the MATLAB code! So I test the ...
2
votes
1answer
112 views

Finite Elements: using preconditioned conjugate gradients with incomplete cholesky decomposition

I have to write a little finite elements code in C. I was asked to implement the conjugate gradients method, which I have done. Now, I am looking to improve further the efficiency of my program by ...
4
votes
3answers
161 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 ...
1
vote
1answer
36 views

Solve system involving unordered triangular matrix

Given a system $Ax = b$, I'm coding a linear solver in Java that takes a triangular matrix $A$ (with 500 to 3,000 rows and columns) and a vector $b$ and solves for $x$. However, the rows and columns ...
0
votes
0answers
47 views

How do I “push” matlab's lsqr solver to a particular solution?

The background to my problem can be found here: Iteratively solving a sparse, ill-conditioned system I have a function that now works well. When I give it test data, I recover the expected result. ...
3
votes
0answers
88 views

Iteratively solving a sparse, ill-conditioned system

I have a sparse (density = 0.2%), ill-conditioned system that I am trying to solve, with no luck. Background I have a sequence of sampled data, where two of every 8 samples have been zeroed due to a ...
3
votes
1answer
89 views

Time complexity of $l_2$-norm of a vector

What is the complexity (in flops, floating-point operations) of taking the $l_2$-norm of vector $\mathbf{v}\in\mathbb{R}^n$ (or $\mathbf{v}\in\mathbb{C}^n$ if a difference exists). We have the ...
9
votes
2answers
172 views

Matrix exponential of a Hamiltonian matrix

Let $A, G, Q$ be real, square, dense matrices. $G$ and $Q$ are symmetric. Let $$H = \begin{bmatrix} A & -G \\ -Q &-A^T \end{bmatrix}$$ be a Hamiltonian matrix. I want to compute the matrix ...
3
votes
1answer
95 views

Solve $A^{-1} b$ when one column is replaced

Given square matrix $A_0$, vector $b$, vector $A_0^{-1}b$ and matrices $A_1, A_2, \dots, A_k$, in which each $A_i$ is generated from $A_{i-1}$ by replacing one single column, I would like to find an ...
2
votes
0answers
60 views

Acceleration of matrix geometric series

Suppose we want to find $x$ such that: $$x=b+Ax$$ where $A$ is a large sparse square matrix with eigenvalues in the unit circle. There are two representations of the solution: 1) $$x=(I-A)^{-1}b,$$...
0
votes
0answers
39 views

How to reduce dimension using CUR Decomposition?

I am trying to understand this paper called High Dimensionality Reduction Using CUR Matrix Decomposition and Auto-encoder for Web Image Classification. I have understood the method proposed for ...
2
votes
1answer
84 views

How we can use CUR decomposition in place of SVD decomposition?

I have understood how CUR and SVD works, but have not been able to understand the following. How can we use CUR in place of the SVD decomposition? Do the $C$ and $R$ matrices in the CUR follow the ...
0
votes
1answer
56 views

Wanting an explanation of the variables in Iterative PCA algorithm

I've been trying to implement the CPU GS-PCA algorithm in this paper . The code starts on page 28 I have a program written a script in python which gives the same output as the C++ program in the ...
3
votes
0answers
39 views

Left eigenvectors using ARPACK

I'm trying to find both the dominant $k$ left and right eigenvectors, that is, $$V_L\mathcal{A} = \Lambda V_L\\ \mathcal{A}V_R = V_R\Lambda\\ V_LV_R = I_{k\times k}$$ $V_L$ being the $k\times N$ ...
0
votes
0answers
34 views

Example of arbitrary precision in Trilinos

I am trying to get Amesos2 in Trilinos working with the arbitrary precision library GMP. This paper http://www.sandia.gov/~srajama/publications/Amesos2_Belos_2012.pdf suggests that it should be ...
8
votes
2answers
80 views

Exploiting patterns in matrix for efficient matrix-vector multiplication

I have the following situation: I have a sequence of vectors $x_1, x_2,.. $ and for each I want to compute the product $Ax_i$ where $A$ is fixed at the outset. Although there is no information about ...
2
votes
1answer
89 views

Modifying solution of system of linear equations

Suppose that we have a linear system of equations $$Ax=b$$ where $A$ is a $3 \times 3$ matrix and $x$ and $b$ are $3$-vectors. Let $y$ denote the solution of this system of equations. I want to ...
1
vote
1answer
61 views

Approximation to Solution of a Linear System of Equations

Consider a linear system, $Ax=b$ where $A$ is the coefficient matrix, $x$ is the unknown vector of variables, and $b$ is a vector of constants in which all entries are same. Is there a way to find ...
5
votes
1answer
132 views

Nystrom approximation of SVD for asymmetric matrices

Suppose I have a symmetric matrix $K$. Subdivide $K$ into pieces as $$K=\begin{pmatrix} K_{11} & K_{12} \\ K_{21} & K_{22}\end{pmatrix},$$ where $K_{21}=K_{12}^\top$. Then, the Nystrom ...
2
votes
1answer
78 views

Which iterative method and preconditioner from petsc should be used when solving linear algebra in parallel?

I am currently trying to parallelize the incompressible flow solver code. However, when I run the code I realise that the parallel code takes much longer time than sequential code to finish one ...
0
votes
0answers
64 views

Forming the Cholesky decomposition of $A=D+X^TX$ without computing $X^TX$ [duplicate]

My understanding from this answer here, is that if I'm attempting to form the Cholesky decomposition of a positive-definite matrix $$A=X^TX$$ then it's best in terms of numerical accuracy to never ...
4
votes
1answer
77 views

Obtaining a feasible solution for underdetermined system of linear equations satisfying inequality constraints

I would like to obtain a feasible solution for an under-determined system of linear equations, $$Ax=b$$ where, $A \in \mathbb{R}^{7\times9}, \, x \in \mathbb{R}^{9\times1}\text{and } b\in\mathbb{R}^...
0
votes
1answer
64 views

How to do a Generalized Complex Schur (or QZ) Decomposition with Eigen C++? [closed]

I would like to do a Generalized Schur (or QZ) decomposition for a pair of complex matrices $A$ and $B$. I found the following class: ...
1
vote
0answers
24 views

What is a performant clustering algorithm for approx 10,000 vectors of approx 30 dimension?

I have a set of real-valed vectors, for example $S = \{v_1, v_2, ..., v_k\}$ $v_i = \begin{pmatrix} age_i \\ height_i \\ weight_i \\ ... \end{pmatrix}$ or whatever. Each vector has on the order of ...
4
votes
2answers
135 views

MATLAB Matrix Multiply Efficiency

I am using MATLAB to prototype a few matrix multiply techniques and compare efficiency. Eventually, I will move the prototype codes to C. It is for a homework assignment where we need to write an ...