Questions tagged [matrix]

For questions about using and representing matrices on a computer in order to solve computational problems. Should generally also include a tag about the specific property/problem you are solving (e.g. [tag:linear-algebra], [tag:eigenvalues], [tag:inverse].

102 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers
297 views

Wanted: sequences of linear systems for recycling Krylov solver analysis

In the solution of sequences of linear systems $$A_ix_i=b_i\quad\text{for}\quad i=1,2,\dots$$ with Krylov subspace methods, data can be recycled from already solved linear systems in order to speed up ...
andrenarchy's user avatar
9 votes
0 answers
526 views

Updating matrix diagonal with Woodbury matrix identity and maintaining numerical accuracy

I have a dense matrix A and its corresponding inverse $A^{-1}$. The Woodbury matrix identity states: $$ (A + UCV)^{-1} = A^{-1} - A^{-1}U(C^{-1} + VA^{-1}U)^{-1}VA^{-1} $$ I wish to perform small ...
Costis's user avatar
  • 1,320
8 votes
0 answers
573 views

Speed and accuracy of Strassen vs Winograd matrix multiplication algorithms

I am doing work which requires as fast matrix multiplication as possible and just want to double-check with this community that the Winograd variant of Strassen's MM algorithm is the fastest practical ...
kreitz's user avatar
  • 91
8 votes
0 answers
435 views

Eigenvalue with largest imaginary part

Iterative eigensolvers such as ARPACK, give the option to find a subset of the eigenvalues which have the largest imaginary part. My question is how do these algorithms work. As I understand it, ...
as2457's user avatar
  • 243
8 votes
0 answers
785 views

What is the source of the error in the Sherman-Morrison formula application?

The Sherman-Morrison formula $$ (A+uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u} $$ results in small errors in relation to the standard matrix inverse operation after each application, ...
rcpinto's user avatar
  • 180
7 votes
0 answers
903 views

Sparse matrix format and sparse-matrix sparse-matrix multiplication

I'm having some performance problems with my code dealing with the multiplication of big sparse matrices (stiffness and aerodynamic influence coefficient matrices). Mainly I have to multiply such ...
murph_sof's user avatar
7 votes
0 answers
336 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 ...
vainia's user avatar
  • 121
6 votes
0 answers
203 views

An invertible matrix that minimizes the norm of the product with a given matrix

Given a fat matrix $B \in \mathbb{C}^{n \times m}$ (where $m > n$) with full row rank, I would like to find (numerically) a full-rank matrix $A$ that minimizes the Frobenius norm of the product $A ...
Kawhi's user avatar
  • 111
6 votes
0 answers
141 views

How does an unpivoted QR fail to reveal rank?

An unpivoted QR factorization produces a triangular factor $R$. A rank-revealing QR factorization is typically done with column pivoting. My question is, how does an unpivoted QR factorization fail to ...
Victor Liu's user avatar
  • 4,480
5 votes
0 answers
45 views

Lowest eigenvalues of a matrix with divergent entries

In high energy physics we oftentimes encounter the following problem. For a given parametrized matrix $\{H_{ij}(\Lambda)\}$, we know that in the limit $\Lambda\to\infty$ some of its entries become ...
mavzolej's user avatar
  • 151
5 votes
0 answers
92 views

Is this a legit way to sample a random matrix spectrum?

In order to undergird a theoretical model concerning many body physics, I want to have exponentially large eigenvalue spectra from the random matrix GOE ensemble. its properties are mainly (i) a ...
Peter Sanctus's user avatar
5 votes
0 answers
106 views

Efficient way to find eigenvalues of complex symmetric matrix with real off-diagonal elements

My goal is to find all eigenvalues (and eigenvectors) in a given range of magnitudes of a complex symmetric matrix with real off-diagonal elements (only diagonal elements are complex). Currently I'm ...
QNA's user avatar
  • 151
5 votes
0 answers
367 views

Polynomial rooting - fast root finding

I need to solve a rooting problem of a polynomial (the order of which is 2(N-1), where N=48). So far I'm using Python Numpy algorithm (that relies on computing the eigenvalues of the companion matrix)...
Luca R's user avatar
  • 61
5 votes
0 answers
527 views

Optimisation of matrix exponential

I have a 7000x7000 sparse matrix (scipy), which I want to exponentiate. I've tried using scipy.sparse.linalg.expm, which works quite well for smaller matrices (takes a few seconds for a 1000x1000 ...
ferros's user avatar
  • 51
5 votes
0 answers
708 views

Generating pseudo-random orthonormal bases for random projection

I am performing series of random projections i.e. projecting the input matrix onto randomly generated orthonormal bases (of much lower dimensionality). The projection is just a matrix multiplication ...
Adam's user avatar
  • 151
5 votes
0 answers
781 views

Perron-Frobenius theorem on general real symmetric matrices

From the Perron-Frobenius theorem, it might be concluded that the spectral radius is the largest eigenvalue for positive matrices, ie, matrices with strictly positive entries. In other words, the ...
usero's user avatar
  • 1,663
5 votes
0 answers
139 views

Probabilistic algorithms for matrix approximation

Considering regular matrix approximation inequality || $A - QQ^TA $|| < e where we try to approximate matrix $A$ by a lower rank orthonormal matrix $Q$. I've read an article on probabilistic ...
ahmethungari's user avatar
4 votes
0 answers
556 views

Fastest matrix library for Android (with GPU is possible)

I was working on an Android app that requires some linear algebra with matrices. The matrices will be somewhat medium-sized as they are not too small or too big. I was originally using jBlas because ...
Aditya Mangalampalli's user avatar
4 votes
0 answers
103 views

Block matrix and DSYRK

I want to compute the matrix $$ A = \sum_{i=1}^N v_i v_i^T $$ where each $v_i$ is a given vector of length $2500$, so that $A$ is $2500 \times 2500$, and my $N$ is about 2 million. Rather than call ...
vibe's user avatar
  • 1,048
4 votes
0 answers
136 views

How to stochastically estimate the trace of a matrix?

Specifically, the diagonal elements (can possibly both positive and negative) of the matrix can be computed efficiently but the total number is large ($\mathcal O(10^{18})$). My first thought about ...
Izzy Vang's user avatar
4 votes
0 answers
1k 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 ...
Set's user avatar
  • 483
4 votes
0 answers
214 views

Alternative to (costly) matrix multiplication

Consider the integral $$2\pi T = -\frac{1}{2} \int_0^{2\pi} A\frac{\partial B}{\partial \xi} \ d\xi$$ where $$A= \sum_{-N}^N i \ sign(n) \ B_n e^{-in\xi}; \quad \quad B= \sum_{-N}^N \ B_n e^{-in\xi}...
Nick P's user avatar
  • 385
4 votes
0 answers
161 views

How big a matrix can we row reduce in reasonable time?

I have very large matrices that I would like to row reduce (I need to keep track of the steps and find a basis of the kernel/image, not just find the rank). The good news is that I work mod 2 and the ...
Bogdan's user avatar
  • 141
4 votes
0 answers
105 views

Tracking for two meshes

I'm dealing with physical simulation (position based dynamic). Now I'm trying to realize tracking for two meshes. In order to explain what does it mean, let's assume that we have two similar meshes: ...
Stepan Loginov's user avatar
3 votes
0 answers
400 views

What is the fastest algorithm for computing log determinant of a PSD matrix? (All possible PSD matrices)

I am diving into some literature to understand which is the best algorithm for computing the log-determinant of a PSD matrix. More generally, I am interested in a list of resources to read, which ...
asdf's user avatar
  • 131
3 votes
0 answers
713 views

What algorithm do BLAS and ATLAS use for matrix multiplication?

I have searched and what I understood was that they use the naive one with several memory and cache optimizations. However, I wanted to know whether they are using the Strassen or the Coppersmith-...
bedo dan's user avatar
3 votes
0 answers
458 views

Computing Small Eigenvalues with Sparse Symmetric Indefinite Mass Matrix

I want the eigenvalues of the following generalized eigenvalue problem: $$ Av = \lambda M v $$ where $A\in\mathbb{R}^{n\times n}$ is sparse, symmetric, and positive semi-definite $M\in\mathbb{R}^{n\...
user3658307's user avatar
3 votes
0 answers
44 views

Reweighted least squares factorization

This is a continuation of the question asked here. I want to solve numerous least squares systems of the form $$ D_i A x \approx D_i b $$ where $D_i$ are $m \times m$ diagonal matrices with positive ...
vibe's user avatar
  • 1,048
3 votes
0 answers
134 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,$$...
cfp's user avatar
  • 131
3 votes
0 answers
144 views

Backward stable algorithm to get orthogonal projection onto the column space of a matrix

I have to find the orthogonal projection of a vector $b$ onto the matrix $A$ of size $m \times n$. In my application, I don't have the luxury of calculating the QR factorization. All I have are ...
Abhay Gupta's user avatar
3 votes
0 answers
62 views

Dominant contributions of a quadratic form

Let $\Sigma$ be a covariance matrix (e.g. symmetric positive definite). For arbitrary vectors $\epsilon$, I need to compute $\chi^2 \equiv \epsilon^\top\Sigma^{-1}\epsilon$, which I do using a ...
yannick's user avatar
  • 375
3 votes
0 answers
66 views

Matrix completion when the eigenvectors are a tensor product?

Suppose we have incomplete observations of the square matrix $X$. Most matrix completion algorithms assume the matrix is low-rank. What if instead we assume the matrix of eigenvectors is a tensor ...
David P's user avatar
  • 33
3 votes
0 answers
213 views

SVD computation with "initial guess"

Suppose I have some matrix A whose SVD I know. Now, I am given B which is A plus some small ...
olamundo's user avatar
  • 599
3 votes
0 answers
432 views

On solution of a class of discrete-time Lyapunov equation for systems with multiplicaitve noise

Let's consider the following equation $$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$ where $p$ is an positive integer and $C$ is a known positive semidefinite matrix. If we augment $F=[F_{1}...F_{p}]$ ...
eolithr's user avatar
  • 31
3 votes
0 answers
182 views

How to accurately decompose positive semidefinite matrix and use the lower triangular part in linear equations

I have $n$ arbitrary $p\times 1$ vectors $x_i$, and $p\times k$ matrices $A_i$, and $n$ $p \times p$ positive semidefinite matrices $S_i$, where some (often most) of the $S_i$'s are same (for example ...
Jouni's user avatar
  • 131
2 votes
0 answers
67 views

Efficient Algorithm for LU-Factorization of Modified Matrix with Last Column Alteration If We Have Its Not-Modified LU-Factorization

Suppose that we have a $n\times n$ matrix $A$. We have its LU-factorization as $A=LU$ (or $PA=LU$ that $P$ is a permutation matrix). Now assume we change the last column of matrix $A$ and denote the ...
Ferran Gonzalez's user avatar
2 votes
0 answers
69 views

Complex matrix logarithm discontinuity by solving inverse Fourier integral by alternative method to FFT

NOTE: This code is a piece of code I am using for a master's thesis, so I do not expect someone to do the work for me, but I gladly accept suggestions of any kind. However, I am trying to get the ...
SimoPape's user avatar
2 votes
0 answers
71 views

When is Lanczos tridiagonalization accurate?

Suppose that we are given a random, symmetric matrix $A$, and a random vector $q$. For concreteness, assume the dimensions of $q$ and $A$ are both $1,000$. I would like to use the Lanczos algorithm to ...
miggle's user avatar
  • 41
2 votes
0 answers
57 views

Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R?

Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R to the end of the diagonal? As an example, consider the following snippet of MATLAB ...
wyer33's user avatar
  • 757
2 votes
0 answers
156 views

Jacobian matrix cutoff in ODE solver

I am studying an implementation of a 3rd semi-implicit Runge Kutta method (siRK3) from the book by Villadsen & Michelsen (1978), Solution of differential equation models by polynomial ...
IPribec's user avatar
  • 597
2 votes
0 answers
69 views

How to solve this boundary value problem which has more unknown than equation on MATLAB

I need your helps about solving the problem below with MATLAB. I am trying to solve 2D Stress Wave Propagation problem by using FDTD(Finite difference time domain) method on the cylindrical coord. I ...
Mechasteel's user avatar
2 votes
0 answers
159 views

If dot product is commutative, why does MATLAB give different answers?

Why does the dot() function in MATLAB return different expressions based on the order in which I pass vectors?
iceburger's user avatar
  • 121
2 votes
0 answers
111 views

Random Orthogonal Matrix Generation

This post is inspired by N. Higham post "What is Random Orthogonal matrix?". In this post, N. Higham links to the two papers: G. W. Stewart, The efficient generation of random orthogonal matrices ...
Anton Menshov's user avatar
  • 8,652
2 votes
0 answers
124 views

How to determine the finite difference coefficient matrix in 2D with periodic BC?

I'm solving a PDE in matlab using ode15s, and since the spatial dimension is 2, and number of variables grow large very quickly, I need to supply the structure of ...
Physicist's user avatar
  • 227
2 votes
0 answers
248 views

Lexicographically order matrix into a vector

I am trying to implement the algorithm contained in this article here. It is about solving a 2 and 2.5D Fredholm integral, focused on bidimensional NMR experiments. I've made significant progress, ...
K.Cl's user avatar
  • 149
2 votes
0 answers
45 views

Inverses of many standard subspaces of one large matrix

i have a large rectangular invertible matrix M (about 5000x5000) and i have a loop in which i do the following for each iteration i (there are about 6000 iterations): i am given a subspace S_i (which ...
bshanks's user avatar
  • 141
2 votes
0 answers
36 views

Minimize number of math operation of a specific matrix vector multiplication?

Let's say we have a Matrix M and a column vector v like below multiply equals Assume we can only perform multiplication, addition and substraction operation. With normal approach we need 3 ...
worldterminator's user avatar
2 votes
0 answers
46 views

Best way of porting code from the GPU to MPI-nodes

I have a program, structured in two parts, $A$ and $B$. Both parts are capable of running as standalone units, and written in C++. $A$ is written for cluster systems, running entirely on CPU-nodes, ...
arc_lupus's user avatar
  • 543
2 votes
0 answers
34 views

Randomized Submatrix of a Sparse Matrix

I have a sparse square matrix $A$ with size $n \times n$ and number of nonzero entries $nnz$. The goal is making a sub-matrix $B$ with $s$ nonzeros which are randomly chosen from $A$. Duplicates are ...
Abaris's user avatar
  • 21
2 votes
0 answers
736 views

finding null space to a complex matrix

I need to solve the following equation: $$ \begin{pmatrix} \frac{\omega^2}{c^2}\varepsilon_x-\mu_z^{-1}k_y^2-\mu_y^{-1}k_z^2 & \mu_z^{-1}k_xk_y & \mu_y^{-1}k_xk_z\\ \mu_z^{-1}k_xk_y &\...
Physicist's user avatar
  • 227