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
0
votes
1answer
70 views

Relation to all-pairs Euclidean distances

Given $d$-dimensional coordinates residing in a matrix $X\in\mathbb{R}^{n\times d}$, the Euclidean distance between items $i$ and $j$ is denoted as $g_{ij}$. Let $c\in\mathbb{R}^d$ denote the centroid ...
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 ...
1
vote
2answers
1k views

What does “Counting algebraic multiplicity” mean?

As stated in the title, I encountered a proof with the final statement of the form "the eigenvalues of A are then $\{\lambda_1+c, \lambda_2, \dots, \lambda_n \},$ counting algebraic multiplicity. ...
0
votes
1answer
283 views

Quickly computing inversion of a large sparse partial stochastic matrix

Suppose I have a sparse stochastic matrix $M$ (with thousands or millions of stochastic column vectors), possibly encoding some links in a web graph. Now I split it into two matrices: $D$ containing ...
2
votes
2answers
119 views

A sufficient number of distances to recover relative positions of n points

On several places I found different claims on a sufficient number of distances to recover relative positions of $n$ points in $d$-dimensional space. For instance, work from http://www.dimitris-...
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 ...
3
votes
2answers
307 views

Computing Permanents of $64 \times 64$ Matrices

I need to compute the Matrix Permanents of several $64 \times 64$, zero-one matrices. I have tried using the built in functions in both Sage and Maple, but both programs return out of memory errors. I ...
13
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. ...
7
votes
3answers
245 views

Wanting to learn about matrix solvers

Edit: I was advised to replace the question with a more specific one. Coming from a very theoretical background, I'm pretty ignorant about what practical matrix solvers exist. (I have been, and will ...
6
votes
2answers
270 views

Derive PCA with SVD

The context is I have a big matrix, 20K * 50K, and I want reduce the dimensionality. In R, it's impossible to apply PCA with more variables(columns) than observations(rows). Therefore, I am trying a ...
4
votes
2answers
78 views

Any reference which summarizes decompositions?

Is there any reference (preferably available online as PDF, Free would be best) which summarizes the various matrix decomposition with their conditions for use, usage, algorithm, complexity and ...
5
votes
2answers
265 views

Out-of-core matrix transpose of row compressed data

Summary: Are there good algorithms for out-of-core dense matrix transpose if each row of the matrix is separately compressed? Details: The matrix is about 1 TB uncompressed, and is roughly but not ...
3
votes
1answer
1k views

Application of an orthogonal matrix to a 3D configuration of point

Suppose a 3D configuration of points is given, $X\in\mathbb{R}^{n\times 3}$, and a matrix $Q\in\mathbb{3\times 2}$, with orthonormal columns. Now, suppose a mapping to 2D is obtained as $$Y=XQ.$$ ...
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 ...
2
votes
1answer
343 views

In Octave, how do I specify that the solution to a matrix equation should be over integers?

In Octave, how do I specify that the solution to a matrix equation should be over integers? I.e., Given matrix $A$, vectors $x$ and $b$; $Ax=b$. Find vector $x=A^{-1}b$ such that all its entries are ...
5
votes
1answer
192 views

What is the difference between MATSEQMAIJ and MATSEQAIJ in PETSc?

What is the difference between MATSEQMAIJ and MATSEQAIJ in PETSc? Also, where can I find more information on each of the MatTypes? I went to the MatType documentation, but it didn't have anything but ...
3
votes
1answer
225 views

3D to 2D projections, a generalization

Given some data points in 3D, $X\in\mathbb{R}^{n\times 3}$, could one say that $$Y=XP,$$ for some $P\in\mathbb{R}^{3\times 2}$ actually corresponds to a particular viewpoint on a 3D data? Basically, ...
4
votes
2answers
153 views

Simplifying some operations on Gram matrices

Suppose two Gram matrices are given $A, B\in\mathbb{R}^{n\times n}$, such that $$A=XX^T,~~~~~~~~~~~~~B=YY^T,$$ for some $X, Y\in\mathbb{R}^{n\times k}$, $k\ll n$. Also, suppose a Gram matrix based on ...
11
votes
1answer
681 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 ...
4
votes
1answer
129 views

Constructing the origin position by transforming distance information

Suppose a set of $n$ points, $n\in M$, is given in some $d-$dimensional space, $X\in\mathbb{R}^{n\times d}$. Among these $n$ points, some $k\in K$ are selected, so $k<n$, and the distances from ...
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 ...
4
votes
0answers
614 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 ...
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 ...
3
votes
0answers
69 views

Understanding how Numpy does SVD [duplicate]

Possible Duplicate: Understanding how Numpy does SVD I have been using different methods to calculate both the rank of a matrix and the solution of a matrix system of equations. I came across the ...
2
votes
1answer
223 views

Proof continuation for rigid transformation on PCA solution

Suppose a matrix $X\in\mathbb{R}^{n\times 3}$ is given as a Principal Component Analysis (PCA) projection from some high dimensional space. The 2D PCA solution on X, say $Y\in\mathbb{R}^{n\times 2}$ ...
7
votes
3answers
8k 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 ...
1
vote
3answers
244 views

Unique coordinates (solutions) in a single Gauss-Seidel iteration

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$ are weighted Laplacian matrices (...
0
votes
1answer
934 views

A Comparison between GMRES, QMR and LU for Dense Matrices

As I see it, there are 3 ways to solve unstructured dense system of equations: GMRES, QMR and LU. Has anyone done a comparison for these three? As far as I know, LU is the preferred choice and it is ...
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....
3
votes
2answers
122 views

Time-stable SO(n) matrix synthesis algorithm

Consider an equation $S(t)b(t) = a$, where $a, b(t) \in S^{n-1}$ are given and the vector $b(t)$ is continuous, i.e. its endpoint traces a continuous curve on the unit sphere. The task is to find ...
3
votes
1answer
863 views

Spectral decomposition with eigenvalue shift

Suppose a square, real and symmetric matrix $G\in\mathbb{R}^{n\times n}$ is given, and it is known to have one zero eigenvalue associated with all ones eigenvector, $1_n$. I'm aware that the (possibly)...
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 ...
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 - \...
4
votes
2answers
4k views

Is there an MPI All Gather operation for matrices?

I have a distributed matrix, in block column format. I know that I can reshape the matrix into one long vector and use an all_gatherv operation. I just wanted to avoid the trouble of having to ...
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\...
4
votes
4answers
225 views

Determining the algorithmic complexity

A few of the iterative matrix algorithms (CG,GMRES etc.) I have authored are acting rather funny. They converge to the right answers but take abnormally long time to run. I am in the process of ...
7
votes
1answer
580 views

Jacobi iteration to reduce the quadratic function

Given certain function $f(X)$ which is quadratic in $X\in\mathbb{R}^{n\times d}$, $$\frac{1}{2}tr(X^TAX) - tr(Y^TBX)$$ for positive definite weighted Laplacian matrices $A, B\in\mathbb{R}^{n\times n}...
4
votes
3answers
218 views

Efficiently computing a few localized eigenvectors

Let $H = \triangle + V(x) : \mathbb{R}^2 \rightarrow \mathbb{R}^2$. I am interested in domain decomposition for an eigenproblem involving $H$. The lowest 1000 eigenfunctions of $H$, $ \psi_i $, can ...
3
votes
2answers
573 views

Unimodular Matrix calculation

I know for a given matrix $M$, there exists a matrix $U$ over the integers with determinant $+1$ or $-1$ such that $UM=E$. I know $E$, but $M$ is not a square matrix. Is there any easy way to get $...
4
votes
2answers
280 views

Is it possible to prove that the off-diagonal blocks of the Cauchy matrix have numerical rank $O(\log n)$?

Suppose we have a $n\times n$ Cauchy matrix of which the $ij$-th entry is given by: $$ A_{ij} = \frac{1}{a_i - b_j} $$ the assumption is that the distance between $\{a_i\}$ and $\{b_j\}$ is greater ...
7
votes
1answer
862 views

Sparse hermitian eigensystems: are there better techniques than Arpack or TRLan?

As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
3
votes
1answer
855 views

Is a checkerboard block decomposition of a matrix useful when solving a linear system with a parallel conjugate gradient method?

According to these lecture notes, a checkerboard block decomposition should exhibit better scalability when applied to parallel matrix-vector multiplication (presumably because of greater cache hit ...
6
votes
2answers
319 views

What guidelines should I use when choosing a scalable linear solver?

There are many different linear solvers, some which work best for diagonally dominant matrices, some for symmetric, some for positive definite ones, some for banded matrices, etc... There are direct ...
4
votes
0answers
134 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 ...
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?
36
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? ...