Skip to main content

Questions tagged [dense-matrix]

Questions about working with or solving equations involving matrices which are known or suspected to have many nonzero elements. Contrast with sparse matrix.

Filter by
Sorted by
Tagged with
2 votes
1 answer
134 views

Tools to compare two matrices with same dimensions

Context: I have two 3D non-random matrices that have the same dimensions. These matrices represent satellite images with 1 band, so their values are strictly positive. They both present areas that ...
Nihilum's user avatar
  • 121
2 votes
1 answer
97 views

Solve linear system for only part of the solution vector

I am using the ScaLAPACK PDGESV routine to solve large dense linear systems distributed over many supercomputer nodes, but ultimately I only need a small portion of the solution vector (e.g. the first ...
quixedjetr's user avatar
0 votes
1 answer
66 views

Solving a linear system whose coefficient matrix is dense but symmetric

For solving a linear system, $Ax = b$. If $A$ is a dense but symmetric $n \times n$ matrix, how much memory is required? $A$ is symmetric, which means only the upper (or lower) triangular part of $n \...
Yonghyun Chung's user avatar
2 votes
0 answers
101 views

How to save multiplication computation time between a dense vector and a not that sparse matrix?

I am trying to compute $\mathbf{X}\mathbf{u}$ for many times in my algorithm, where $\mathbf{X}\in \mathbb{R}^{n\times m}$ and $\mathbf{u} \in \mathbb{R}^{m}$. The problem is that, during the ...
Xun Maoapo's user avatar
1 vote
0 answers
214 views

performance comparison between PETSc and SLATE

We want to start a new project to solve a large-scale inverse problem (O(10^6) number of parameters) to invert for subsurface wave speeds. We will use FEM to solve forward and adjoint PDEs. In our ...
user2348209's user avatar
4 votes
1 answer
190 views

Trace of inverse from LU decomposition

Given an LU decomposition of $A\in \mathbb{R}^{n\times n}$, is there a way to compute $\operatorname{trace}(A^{-1})$ with lower complexity than that of the inversion ($O(n^3)$ in practice)? This ...
Federico Poloni's user avatar
8 votes
2 answers
721 views

Is there an iterative solver for dense matrices with possible zero diagonal entries?

Is there an iterative solver that can handle potentially zero entries on the central diagonal? I am implementing a polynomial fitting algorithm (up to $10^{th}$-order) and my matrix is a "...
niran90's user avatar
  • 233
0 votes
1 answer
220 views

Library to solve dense linear system with GMRES

I have a fortran 90 code and I want to solve a dense linear system with GMRES. I would prefer the restarted GMRES with preconditioning. Is there some library that you know of that I could use? Now I ...
Riri's user avatar
  • 43
4 votes
0 answers
105 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,058
4 votes
1 answer
328 views

Fast matrix multiplication with matrix elements computed on-the-fly (without forming the matrix)

Is there any library or routine for high-performance matrix-matrix product, where the matrix elements are computed on-the-fly using a given function of $i$ and $j$? More specifically, in the problem ...
fcdimitr's user avatar
  • 141
15 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
  • 163
6 votes
2 answers
319 views

inertia count sparse matrix with dense low-rank perturbation

I would like to determine the number of negative eigenvalues (inertia count) of the $(N \times N)$ symmetric real matrix $K - \sigma M$, with $K$ a positive-definite sparse matrix and $M$ a positive-...
Olivier's user avatar
  • 81
8 votes
2 answers
1k 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 ...
Sam Hatfield's user avatar
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
1 vote
1 answer
66 views

Optimal algorithm choice for mixed diagonal/dense problem

$$ \text{Let}\\ A, B \in \mathbb{C}^{n \times n} \text{ and } \hat{\alpha}, \hat{\beta} \in \mathbb{C}^{n}, \hat{f} \in \mathbb{C}^{2n} \\ \text{Find }\\ \underline{\mathbf{x}} \in \mathbb{C}^{2n} \...
java4ever's user avatar
1 vote
0 answers
77 views

Parallel dense solve with submatrices from mesh refinement with Petsc

For a Bounday Element Method problem I require the solution of a system of linear equations with multiple right-hand sides. Though this is a dense system, I still want to do it via Petsc in parallel. ...
Toon's user avatar
  • 31
1 vote
1 answer
193 views

GPU libraries for integer matmul | overflow tolerated

Are there any high performance integer BLAS libraries that implement matrix multiplication i.e. i32gemm and i64gemm ? I need to use them for a cryptographic application and can tolerate overflows, i.e....
kesari's user avatar
  • 287
0 votes
1 answer
109 views

Need clarification on a piece of book excerpt about spectral element method!

I am reading "Using MPI (3rd edition)" from William Gropp, where in chapter 4 application section 4.13, it introduces an MPI application Nek5000/NekCEM which is based on spectral element method (SEM) ...
user123's user avatar
  • 679
1 vote
2 answers
2k views

Comparison between two matrices

I have a large dense matrix $A$. For simplicity in simulation purposes and application demand, I induced sparsity by replacing lower/insignificant values by zero and reordering it in block diagonal ...
Teju's user avatar
  • 19
1 vote
2 answers
267 views

How is the dense system usually dealt with in spectral method?

Unlike finite element (FEM) or finite difference methods (FDM), where the original PDE is transformed into a sparse linear system, spectral methods return a dense linear system. For a large system, it'...
user123's user avatar
  • 679
5 votes
2 answers
1k views

Smart way to multiply 3 matrices

I have a quantum mechanics simulation where I need to multiply three matrices that look like this: $$\rho(t_1)=U^\dagger \rho(t_0) \, U$$ where $U^\dagger$ is the hermitian conjugate of $U$. This ...
The Quantum Physicist's user avatar
1 vote
2 answers
1k views

Compute all eigenvectors and eigenvalues of small symmetric matrices

My problem is to compute eigenvectors and eigenvalues of a lot of small (n < 30) symetric, positive definite matrices. So far I am using LAPACK's DSYEV. The priority is speed more than accuracy. ...
mookid's user avatar
  • 111
0 votes
1 answer
145 views

Discretized matrix from the integral kernel function

Recently, I read a paper [1] and then I want to handle the two-dimensional linear integro-differential equation \begin{equation*} -\triangle u + q\Big(\frac{\partial u}{\partial x} + \frac{\partial u}{...
Hsien-Ming Ku's user avatar
1 vote
1 answer
806 views

Preconditioning of two step iteration for dense matrices

I would like to solve a dense linear system the form in python $$ L\left(\boldsymbol{x}\right):=\left[\gamma^+\left[\boldsymbol{A}+\frac{1}{2}\boldsymbol{B}^{-1}\right] +\gamma^-\left[\boldsymbol{A}-\...
sebastian_g's user avatar
18 votes
2 answers
15k views

Complexity of matrix inversion in numpy

I am solving differential equations that require to invert dense square matrices. This matrix inversion consumes the most of my computation time, so I was wondering if I am using the fastest algorithm ...
physicsGuy's user avatar
1 vote
2 answers
1k views

Parallelization of element-wise matrix multiplication

I use Armadillo as an interface to OpenBLAS. In my current program, I have a loop, in which I do multiplications of the form ...
The Quantum Physicist's user avatar
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
2 votes
2 answers
2k views

Solve large dense positive-definite linear system

Which method should I choose to solve a large (~20 000 variables) dense symmetric positive-definite, possibly ill-conditioned, system of linear equations? The system will be solved for two vectors. I'...
Piotr M's user avatar
  • 21
0 votes
1 answer
173 views

Help me analyze the computational cost of two kinds of operations

everyone, I have a question about computational costs for a algorithm. That is: I have two vectors $u_n,\ v_n\in \mathbb{C}^N$, a matrix $A\in \mathbb{C}^{N\times N}$ (can be both sparse and dense) ...
Hsien-Ming Ku's user avatar
3 votes
3 answers
1k views

Large overdetermined system of linear equations

I'm looking for a method to solve a large overdetermined system of linear equations in a least squares sense. The matrix is dense. I'd like to use a method that works even with limited memory (we can'...
mrgloom's user avatar
  • 213
6 votes
1 answer
669 views

Efficient RQ decomposition

I have an upper trapezoidal matrix stored in column major format. That is, my matrix looks like this: I'd like to RQ decompose it, and store Q in the rectangular part of my upper trapezoidal matrix. ...
Jay Lemmon's user avatar
4 votes
1 answer
2k views

Fast way to compute all eigenvalues of a dense Hermitian matrix

I am finding the eigenvalues of dense NxN Hermitian matrix which is calculated from a density operator in quantum physics. All the eigenvalues are needed as I need to calculate the sum of the absolute ...
unsym's user avatar
  • 198
5 votes
2 answers
528 views

Spectral decomposition of symmetric matrix

What is a good direct method to compute the spectral decomposition / Schur decomposition / singular decomposition of a symmetric matrix? "Direct" means as in LU decomposition, Cholesky decomposition, ...
shuhalo's user avatar
  • 3,680
1 vote
2 answers
233 views

Rearrange a dense distance matrix to a 2x2 non-perfect block diagonal form

I have a distance matrix (square, symmetrical, non-negative, dense). I want to split the objects into two well-connected groups. Mathematically speaking, I want to group (re-arrange) the rows/columns ...
Ark-kun's user avatar
  • 131
2 votes
3 answers
291 views

Dense distributed matrix

A dense matrix is distributed for parallel computation column-wise, then multiplied from left & right by sparse matrices. What would be appropriate c++ libraries for these tasks?
user66081's user avatar
5 votes
1 answer
184 views

Computing eigendecomposition of a Hermitian matrix that is almost unitary

I have a dense Hermitian matrix that is approximately unitary, so it has eigenvalues that are $\sim \pm1$. I would like to compute all the eigenvectors corresponding to the $+1$ eigenvalue (not ...
Victor Liu's user avatar
  • 4,480
1 vote
0 answers
99 views

Is it possible to construct such a symmetric matrix with desired eigenvalues?

Suppose a real, dense and asymmetric square matrix $A\in\mathbb{R}^{n\times n}$, all its eigenvalues $\lambda_i \in \mathbb R$ Is it possible to construct a symmetric matrix $B\in\mathbb{R}^{n\times ...
LCFactorization's user avatar
2 votes
0 answers
65 views

Are the eigenvalues of the product matrix of two real symmetric square matrices also real values?

Suppose $A,B \in \mathbb{R}^{n\times n}; A=A^T, B=B^T$, let $C = AB, D =BA$, If we have all the real eigenvalues of $A$ and $B$, e.g. the eigenvalue decomposition of them: $A=P\Lambda_1 P^T$, $B=Q\...
LCFactorization's user avatar
1 vote
1 answer
2k views

How can I reuse the SVD of matrix A to solve LS problems for both A and its transpose via Eigen C++?

If $A\in R^{m\times n}, b\in R^m, c\in R^n$, if I need to solve the least square problems via SVD of $A$ and $A^T$, i.e. I need to solve the least square solutions to following linear systems via ...
LCFactorization's user avatar
10 votes
1 answer
5k views

full rank update to cholesky decomposition

Let $A$ be a real, symmetric, positive definite matrix. It has at least 500 rows, possibly much more. I compute its Cholesky decomposition, which allows me to calculate $det(A)$ $A^{-1}X$ for some ...
yannick's user avatar
  • 375
4 votes
1 answer
1k views

LU Decomposition of PSD Matrix + Diagonal Matrix

If I have a psd, symmetric matrix $\mathbf{A}$ and I need to do LU decomps on $\mathbf{B_i}= \mathbf{A} + \mathbf{D_i}$ (where $\mathbf{D_i}$ is a diagonal psd matrix, where $\mathbf{D_i}$ changes ...
John Liechty's user avatar
3 votes
3 answers
137 views

Smoothly varying dense matrices arising from computational science

I have written an algorithm to solve a dense system with smoothly varying entries. This means I assume there is no large jump from any entry to its neighbors. I would love to use real-application-...
Mai's user avatar
  • 41
6 votes
2 answers
822 views

What are the most common dense matrix storage formats?

I'm looking to write some code to read in a dense matrix from a file, and I was wondering what are the most common storage formats that my code should support?
srabidoux's user avatar
3 votes
2 answers
172 views

Computing sparse matrix products into a dense result

I need to assemble a matrix (in dense form, of moderate size, say dimension 1000) which is most easily expressed as the product of several (4) sparse matrices. These matrices are most easily expressed ...
Victor Liu's user avatar
  • 4,480
6 votes
3 answers
7k views

Algorithm for Principal Eigenvector of a Real Symmetric 3x3 Matrix

I have a 3x3 covariance matrix (so, real, symmetric, dense, 3x3), I would like it's principal eigenvector, and speed is a concern. Is there a fast algorithm for this specific problem? I've seen ...
anjruu's user avatar
  • 203
7 votes
4 answers
3k views

computing the determinant of a dense nonsymmetric 100x100 matrix having very big and very small eigenvalues

The motivation for my question is the following: in one of Project Euler questions there is a need to count the spanning trees of a rectangular grid graph of dimension 100x500. By the Matrix-Tree ...
John Donn's user avatar
  • 223
11 votes
1 answer
1k views

Solving huge dense linear system?

Is there any hope in solving the following linear system efficiently with an iterative method? $A \in \mathbb{R}^{n \times n}, x \in \mathbb{R}^n, b \in \mathbb{R}^n \text{, with } n > 10^6$ $Ax=...
yon's user avatar
  • 213
10 votes
2 answers
858 views

Diagonalization of Dense Ill Conditioned Matrices

I am trying to diagonalize some dense, ill-conditioned matrices. In machine precision, results are inaccurate (returning negative eigenvalues, eigenvectors do not have the expected symmetries). I ...
Leigh's user avatar
  • 101
5 votes
2 answers
761 views

Largest invertible dense matrix with standard solvers such as Lapack

I have a matrix which is complex symmetric. It is around 50,000 elements per side. It is a Method of Moments matrix. Is it feasible to use a standard direct solver such as Lapack to do a matrix ...
Costis's user avatar
  • 1,320