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].

Filter by
Sorted by
Tagged with
38 votes
6 answers
2k views

Symbolic software packages for Matrix expressions?

We know that $\mathbf A$ is symmetric and positive-definite. We know that $\mathbf B$ is orthogonal: Question: is $\mathbf B \cdot\mathbf A \cdot\mathbf B^\top$ symmetric and positive-definite? ...
MRocklin's user avatar
  • 3,088
37 votes
2 answers
12k views

why is A*v+B*v faster than (A+B)*v?

$A$ and $B$ are $n \times n$ matrices and $v$ is a vector with $n$ elements. $Av$ has $\approx 2n^2$ flops and $A+B$ has $n^2$ flops. Following this logic, $(A+B)v$ should be faster than $Av+Bv$. Yet,...
Sam Christensen's user avatar
30 votes
11 answers
11k views

Robust algorithm for $2 \times 2$ SVD

What is a simple algorithm for computing the SVD of $2 \times 2$ matrices? Ideally, I'd like a numerically robust algorithm, but I'll like to see both simple and not-so-simple implementations. C code ...
lhf's user avatar
  • 966
29 votes
4 answers
19k views

Dealing with the inverse of a positive definite symmetric (covariance) matrix?

In statistics and its various applications, we often calculate the covariance matrix, which is positive definite (in the cases considered) and symmetric, for various uses. Sometimes, we need the ...
Benjamin Allévius's user avatar
20 votes
2 answers
3k views

Practical example of why it is not good to invert a matrix

I am aware about that inverting a matrix to solve a linear system is not a good idea, since it is not as accurate and as efficient as directly solving the system or using LU, Cholesky or QR ...
Manu's user avatar
  • 459
19 votes
3 answers
3k views

Why do we usually not want the eigenvalues of non-symmetric matrices?

I came across this line in a class note I am reading where it discusses finding eigenvalues of matrices. In reality we don't go all the way with Arnoldi. We stop at a decent value of 𝑘. Then the 𝑘 ...
CuriousMind's user avatar
19 votes
4 answers
9k views

Row major versus Column major layout of matrices

In programming dense matrix computations, is there any reason to choose a row-major layout of the over the column-major layout? I know that depending on the layout of the matrix chosen, we need to ...
smilingbuddha's user avatar
18 votes
4 answers
4k views

Why can't Householder reflections diagonalize a matrix?

When computing the QR factorization in practice, one uses Householder reflections to zero out the lower portion of a matrix. I know that for computing eigenvalues of symmetric matrices, the best you ...
Victor Liu's user avatar
  • 4,480
18 votes
5 answers
8k views

What is the best way to determine the number of non zeros in sparse matrix multiplication?

I was wondering whether there is a fast and efficient method to find the number of non zeros in advance for sparse matrix multiplication operation assuming both matrices are in CSC or CSR format. I ...
Recker's user avatar
  • 333
18 votes
3 answers
10k views

Efficient computation of the matrix square root inverse

A common problem in statistics is computing the square root inverse of a symmetric positive definite matrix. What would be the most efficient way of computing this? I came across some literature (...
tchakravarty's user avatar
16 votes
2 answers
14k views

In FEM, why is the stiffness matrix positive definite?

In FEM classes, it's usually taken for granted that the stiffness matrix is positive definite, but I just can't understand why. Could anyone give some explanation? For instance, we can consider the ...
user123's user avatar
  • 679
16 votes
2 answers
2k views

Estimation of condition numbers for very large matrices

Which approaches are used in practice for estimating the condition number of large sparse matrices?
Allan P. Engsig-Karup's user avatar
16 votes
3 answers
5k views

Single versus double floating-point precision

Single precision floating point numbers take up half the memory and on modern machines (even on GPUs it seems) operations can be done with them at almost twice the speed compared to double precision. ...
Costis's user avatar
  • 1,320
15 votes
3 answers
3k views

Why isn't my Matrix-Vector Multiplication Scaling?

Sorry for the long post but I wanted to include everything that I thought was relevant in the first go. What I want I am implementing a parallel version of Krylov Subspace Methods for Dense Matrices. ...
Inquest's user avatar
  • 3,384
15 votes
2 answers
46k views

What is the fastest algorithm for computing the inverse matrix and its determinant for positive definite symmetric matrices?

Given a positive definite symmetric matrix, what is the fastest algorithm for computing the inverse matrix and its determinant? For problems I am interested in, the matrix dimension is 30 or less. ...
Orders's user avatar
  • 303
15 votes
2 answers
7k views

Compute all eigenvalues of a very big and very sparse adjacency matrix

I have two graphs with nearly n~100000 nodes each. In both graphs, each node is connected to exactly 3 other nodes so the adjacency matrix is symmetric and very sparse. The hard part is I need all ...
Mahdi's user avatar
  • 253
14 votes
3 answers
5k views

Rule of thumb for sparse vs dense matrix storage

Suppose I know the expected sparsity of a matrix (i.e. the number of non-zeros / total possible number of non-zeros). Is there a rule of thumb (perhaps approximate) for deciding whether to use sparse ...
josh_eime's user avatar
  • 153
13 votes
2 answers
3k views

How is the SVD of a matrix computed in practice

How does MATLAB, for instance, calculate the SVD of a given matrix? I assume the answer probably involves computing the eigenvectors and eigenvalues of A*A'. If ...
olamundo's user avatar
  • 599
13 votes
2 answers
2k views

Does the "cofactor technique" for inverting a matrix have any practical significance?

The title is the question. This technique involves using the "matrix of cofactors", or "adjugate matrix", and gives explicit formulae for the components of the inverse of a square matrix. It is not ...
Stefan Smith's user avatar
13 votes
5 answers
2k views

Calculation of the sparsity structure for finite element matrices

Question: What methods are available to accurately and efficiently calculate the sparsity structure of a finite element matrix? Info: I'm working on a Poisson Pressure Equation solver, using Galerkin'...
John Edwardson's user avatar
12 votes
4 answers
3k views

Finding the square root of a Laplacian matrix

Suppose the following matrix $A$ is given $$ \left[\begin{array}{ccc} 0.500 & -0.333 & -0.167\\ -0.500 & 0.667 & -0.167\\ -0.500 & -0.333 & 0.833\end{array}\right]$$ with ...
usero's user avatar
  • 1,663
12 votes
5 answers
3k views

Repeatedly solving $\mathbf{A} \mathbf{x} = \mathbf{b}$ with same $\mathbf{A}$, different $\mathbf{b}$

I am using MATLAB to solve a problem that involves solving $\mathbf{A} \mathbf{x}=\mathbf{b}$ at every timestep, where $\mathbf{b}$ changes with time. Right now, I am accomplishing this using MATLAB'...
Doubt's user avatar
  • 423
12 votes
5 answers
652 views

Rapidly determining whether or not a dense matrix is of low rank

In a software project that I'm working on, certain computations are vastly easier for dense low-rank matrices. Some problem instances involve dense low-rank matrices, but they're given to me in full, ...
Brian Borchers's user avatar
12 votes
4 answers
1k views

Libraries for solving Lyapunov's equation

The following matrix equation $$B\Sigma + \Sigma B^T + C = 0$$ in $\Sigma$ $-$ for given $B$ and $C$ matrices $-$ appears in my work as a characterization of a covariance matrix. I have learned that ...
NRH's user avatar
  • 221
12 votes
1 answer
545 views

Algorithms for Large Sparse Integer Matrices

I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
jgonagle's user avatar
  • 123
11 votes
3 answers
10k views

Gershgorin Circle Theorem to estimate the eigenvalues

In order to estimate the eigenvalues of a real symmetric $n\times n$ matrix, I intend to use the Gershgorin Circle Theorem. Unfortunately, the examples one might find on the internet are a bit ...
usero's user avatar
  • 1,663
11 votes
3 answers
1k views

Testing if two 12x12 matrices have the same determinant

I am given a $12 \times 12$ matrix $Q$ that is symmetric, invertible, positive definite and dense. I need to test if $$\det(Q) = \det(12I-Q-J) \; \; (1)$$ where $J$ is the all ones matrix. I am ...
Jernej's user avatar
  • 458
11 votes
1 answer
1k views

Why SVD is talk about less than QR and LU for sparse matrix?

For example the C++ sparse matrix libraries I used -- Eigen and SuiteSparse, they seem not to have any SVD funcitionality for sparse matrix. So just curious, is SVD more difficult than QR/LU for ...
user5302's user avatar
  • 211
11 votes
3 answers
1k views

What is the reason that LAPACK uses $\tau$ in QR decomposition (instead of normalizing the reflection vector)?

LAPACK's QR routine stores Q as Householder reflectors. It scales the reflection vector $v$ with $1/v_1$, so the first element of the result becomes $1$, so it doesn't have to be stored. And it stores ...
geza's user avatar
  • 211
11 votes
3 answers
2k views

What's the current state of the art regarding algorithms for the singular value decomposition?

I'm working on a header-only matrix library to provide some reasonable degree of linear algebra capability in as simple a package as possible, and I'm trying to survey what the current state of the ...
gct's user avatar
  • 211
11 votes
1 answer
4k views

weighted SVD problem?

Given two matrices $A$ and $B$, I'd like to find vectors $x$ and $y$, such that, $$ \min \sum_{ij} (A_{ij} - x_i y_j B_{ij})^2. $$ In matrix form, I'm trying to minimize the Frobenius norm of $A - \...
Memming's user avatar
  • 870
11 votes
2 answers
2k 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 ...
DerZwirbel's user avatar
11 votes
1 answer
1k views

Projecting out the null-space of $A$ from $b$ in $Ax=b$

Given the system $$Ax=b,$$ where $A\in\mathbb{R}^{n\times n}$, I read that, in case Jacobi iteration is used as a solver, the method will not converge if $b$ has a non-zero component in the null-space ...
usero's user avatar
  • 1,663
11 votes
1 answer
7k views

How to compute Singular value decomposition of a large matrix with Python

Language: Python3 Problem: I have a matrix Q of shape [51200 rows x 51200 cols] stored in a binary file, each of the element in this matrix has a data type of complex64. To load the data into memory I ...
SAM's user avatar
  • 111
10 votes
3 answers
6k views

MATLAB matrix multiplication (the best computational approach)

I have to make a coordinates transformation between two reference systems (axes). For that, three matrices ($3\times3$) have to be multiplied due to some intermediate axes being used. I have thought ...
julianfperez's user avatar
10 votes
2 answers
7k views

How to find the nearest/a near positive definite from a given matrix?

I'm given a matrix. How do I find the nearest (or a near) positive definite from it? The matrix can have complex eigenvalues, not be symmetric, etc. However, all its entries are real valued. The ...
An old man in the sea.'s user avatar
10 votes
1 answer
2k views

Solving a simple Ax=b system in parallel with PETSc

I am new to the PETSc package. I have a ~4000x4000 matrix A in matrix-market format and I want to get PETSc to solve this using multiple processors. I know how to solve the system on a single ...
smilingbuddha's user avatar
10 votes
2 answers
2k views

Safe application of iterative methods on diagonally dominant matrices

Suppose the following linear system is given $$Lx=c,\tag1$$ where $L$ is the weighted Laplacian known to be positive $semi-$definite with a one dimensional null space spanned by $1_n=(1,\dots,1)\in\...
usero's user avatar
  • 1,663
10 votes
3 answers
4k views

Calculating the log-determinant of a large sparse matrix

I need to calculate $\log(\det (\mathbf M_i))$ where the $\mathbf M_i$'s are large sparse matrices, which are real, symmetric and positive semi-definite. I hope to have between $10$ and $100$ of ...
yohbs's user avatar
  • 267
10 votes
4 answers
573 views

Are there any quad-double arithmetic sparse matrix package?

I am working on some ill-conditioned large sparse linear system of equations. I want to use double-double arithmetic or quad-double arithmetic to solve them. I know that there is a package named MPACK ...
Hanyu Ye's user avatar
  • 191
10 votes
1 answer
971 views

The fast, and The Backward-Stable (left) $3\times 3$ matrix inverse

I need to compute a lot of $3\times3$ matrix inverses (for Newton iteration polar decomposition), with very small number of degenerate cases ($<0.1\%$). Explicit inverse (via matrix minors divided ...
Sergiy Migdalskiy's user avatar
10 votes
1 answer
329 views

Is it possible to express an arbitrary tensor contraction in terms of BLAS routines?

I noticed that libraries like numpy and pytorch are able to perform arbitrary tensor contractions at speeds similar to comparably sized matrix multiplications. This leads me to believe that underneath ...
ilya's user avatar
  • 111
9 votes
6 answers
13k views

Super C++ optimization of matrix multiplication with Armadillo

I'm using Armadillo to do very intensive matrix multiplications with side lengths $2^n$, where $n$ can be up to 20 or even more. I'm using Armadillo with OpenBLAS for matrix multiplication, which ...
The Quantum Physicist's user avatar
9 votes
2 answers
4k views

Parallel computation of big covariance matrices

We need to compute covariance matrices with sizes ranging from $10000\times10000$ to $100000\times100000$. We have access to GPUs and clusters, we wonder what is the best parallel approach for ...
Open the way's user avatar
9 votes
4 answers
881 views

Checking singularity of a matrix

Suppose that we don't know $n \times n$ matrix $A$ explicitly but we are only able to compute products $Ax$ where $x$ is a column vector with $n$ elements. Is there an algorithm to determine whether $...
tohoyn's user avatar
  • 331
9 votes
1 answer
1k views

Why is it that SVD routines on nearly square matrices run significantly faster than if the matrix was highly non square?

In Python / Matlab, if you run a routine for SVD on a significantly non-square matrix, X, such as X.shape = (2,15000) you will ...
tisPrimeTime's user avatar
9 votes
3 answers
5k views

Fastest algorithm to compute the condition number of a large matrix in Matlab/Octave

From the definition of condition number it seems that a matrix inversion is needed to compute it, I'm wondering if for a generic square matrix (or better if symmetric positive definite) is possible to ...
linello's user avatar
  • 273
9 votes
2 answers
879 views

Continuity of eigenvectors of parametric matrix

I have $n$-dimensional matrices $\mathrm{\hat{H}}(\vec{k})$ depending on vector parameter $\vec{k}$. Now, eigenvalue routines return eigenvalues in no particular order (they are usually sorted), but ...
tomic's user avatar
  • 91
9 votes
1 answer
532 views

Least-squares for a diagonal matrix

This is a follow-up to a different question I asked with more detail. For $v\in\mathbb{R}^n$, denote $D_v\in\mathbb{R}^n$ as the diagonal matrix with elements in $v$. Given a "tall" matrix $B\in\...
Justin Solomon's user avatar
9 votes
1 answer
2k views

Solving system of linear equations with cyclic tridiagonal matrix

I have this problem in my textbook: Suggest efficient algorithm for solving system of linear equations with cyclic three-diagonal matrix, that is of the form: \begin{bmatrix} a_1&b_1&0&...
xan's user avatar
  • 315

1
2 3 4 5
13