Questions tagged [matrix]

Matrix is a rectangular array of elements (e.q. numbers, symbols, or expressions), arranged in columns and rows.

Filter by
Sorted by
Tagged with
35
votes
6answers
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? ...
27
votes
4answers
15k 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 ...
25
votes
10answers
7k 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 ...
17
votes
5answers
6k 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 ...
16
votes
4answers
5k 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 ...
16
votes
4answers
2k 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 ...
16
votes
2answers
781 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 ...
15
votes
3answers
2k 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....
15
votes
2answers
1k views

Estimation of condition numbers for very large matrices

Which approaches are used in practice for estimating the condition number of large sparse matrices?
15
votes
3answers
6k 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 (...
13
votes
2answers
1k 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 ...
13
votes
4answers
258 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, ...
13
votes
5answers
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'...
12
votes
5answers
2k 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'...
12
votes
3answers
4k 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. ...
12
votes
3answers
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 ...
12
votes
2answers
1k 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 ...
12
votes
1answer
436 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 ...
11
votes
4answers
2k 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 ...
11
votes
2answers
2k 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 ...
11
votes
3answers
807 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 ...
11
votes
3answers
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 ...
11
votes
1answer
2k 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 - \...
11
votes
1answer
665 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 ...
10
votes
3answers
5k 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 ...
10
votes
1answer
1k 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 ...
10
votes
1answer
930 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 ...
10
votes
4answers
340 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 ...
10
votes
2answers
432 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 ...
9
votes
2answers
3k 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 ...
9
votes
2answers
6k 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 ...
9
votes
3answers
3k 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 ...
9
votes
1answer
26k 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. ...
9
votes
3answers
199 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 ...
9
votes
2answers
1k 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\...
9
votes
1answer
229 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 ...
9
votes
1answer
394 views

Algorithm to calculate the exponential of an Hessenberg matrix

I am interested in computing the solution of a lage system of ODEs using a krylov method as in [1]. Such method involve functions related to the exponential (the so-called $\varphi$-functions). It ...
8
votes
6answers
10k 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 ...
8
votes
3answers
506 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 ...
8
votes
2answers
10k views

Rearrange an ordinary matrix to block diagonal form

Is there an algorithm to rearrange a matrix into block diagonal form, given that the matrix is block diagonal in nature but randomized with an unwise choice of basis? In particular, are there any ...
8
votes
1answer
2k views

How to get sparse complex matrices from my code to PETSc efficiently

What is the most efficient way to get a complex sparse matrix from my Fortran code to PETSc? I understand that this is problem dependent, so I tried to give as many relevant details as possible below. ...
8
votes
1answer
164 views

Sudden drops in matrix multiplication performance

I've been reading about implementing dense matrix multiplication when the matrix doesn't fit in cache. One of the graphs I've seen (slide 9 from these slides) shows sudden drops in performance using ...
8
votes
2answers
512 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 ...
8
votes
1answer
1k 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&...
8
votes
2answers
101 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 ...
8
votes
1answer
244 views

Are there improved method of computing the following expression?

given a symmetric matrix $Y \in \mathbb{R}^{n \times n}$, and an arbitrary matrix $X \in \mathbb{R}^{n \times n}$, and a vector $v \in \mathbb{R}^{n \times 1}$, is it possible to compute the following ...
8
votes
1answer
8k views

Matlab solution for implicit finite difference heat equation with kinetic reactions

I am trying to model heat conduction within a wood cylinder using implicit finite difference methods. The general heat equation that I'm using for cylindrical and spherical shapes is: Where p is the ...
8
votes
1answer
264 views

Fast computation of component-wise $\exp(-XY^T)G$ for random $G$

I have the following question: Suppose I have two matrices $X, Y$ both of size $m\times p$ and a random i.i.d Gaussian matrix $G$ of size $m \times k$, $m\gg p>k$. Is there a fast way to compute $...
8
votes
0answers
213 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 ...
8
votes
0answers
337 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 ...