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].
103
questions with no upvoted or accepted answers
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 ...
- 231
9
votes
0
answers
529
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 ...
- 1,330
8
votes
0
answers
593
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 ...
- 91
8
votes
0
answers
441
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, ...
- 243
8
votes
0
answers
795
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, ...
- 180
7
votes
0
answers
911
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 ...
- 71
7
votes
0
answers
338
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 ...
- 121
6
votes
0
answers
205
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 ...
- 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 ...
- 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 ...
- 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 ...
5
votes
0
answers
107
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 ...
- 151
5
votes
0
answers
376
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)...
- 61
5
votes
0
answers
530
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 ...
- 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 ...
- 151
5
votes
0
answers
782
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 ...
- 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 ...
- 151
4
votes
0
answers
568
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 ...
4
votes
0
answers
748
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-...
- 51
4
votes
0
answers
104
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 ...
- 1,058
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 ...
- 61
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 ...
- 503
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}...
- 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 ...
- 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: ...
- 289
3
votes
0
answers
407
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 ...
- 131
3
votes
0
answers
460
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\...
- 183
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 ...
- 1,058
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,$$...
- 131
3
votes
0
answers
145
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 ...
- 41
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 ...
- 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 ...
- 33
3
votes
0
answers
214
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 ...
- 599
3
votes
0
answers
437
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}]$ ...
- 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 ...
- 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 ...
- 125
2
votes
0
answers
72
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 ...
- 21
2
votes
0
answers
73
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 ...
- 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 ...
- 767
2
votes
0
answers
157
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 ...
- 607
2
votes
0
answers
70
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 ...
- 21
2
votes
0
answers
162
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?
- 121
2
votes
0
answers
112
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 ...
- 8,672
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 ...
- 227
2
votes
0
answers
254
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, ...
- 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 ...
- 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 ...
- 123
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, ...
- 553
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 ...
- 21
2
votes
0
answers
746
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 &\...
- 227