Questions tagged [linear-algebra]

Questions on the algorithmic/computational aspects of linear algebra, including the solution of linear systems, least squares problems, eigenproblems, and other such matters.

Filter by
Sorted by
Tagged with
30
votes
5answers
25k views

Permute a matrix in-place in numpy

I want to modify a dense square transition matrix in-place by changing the order of several of its rows and columns, using python's numpy library. Mathematically this corresponds to pre-multiplying ...
12
votes
1answer
271 views

Algorithms for linear system of ODEs

I wonder: what is the best algorithm to solve \begin{equation} \frac{du}{dt} = Au \end{equation} Where $A$ is a real $n\times n$ matrix. A is not explicitly time-dependent, usually sparse but not ...
12
votes
2answers
3k views

What are the fastest available implementations of BLAS/LAPACK or other linear algebra routines on GPU systems?

nVidia, for example, has CUBLAS, which promises 7-14x speedup. Naively, this is nowhere near the theoretical throughput of any of nVidia's GPU cards. What are the challenges in speeding up linear ...
29
votes
4answers
18k 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 ...
3
votes
2answers
210 views

Efficiently changing basis on many diagonal matrices

I have to perform a [complex] basis transformation on a large number of [real] diagonal matrices: $$ \langle b_i | A | b_j \rangle = \sum_k \langle b_i | \bar{b}_k\rangle \langle\bar{b}_k | A | \bar{b}...
8
votes
1answer
184 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 ...
3
votes
1answer
94 views

High-dimensional representation of arbitrary input

Given a symmetric matrix $A\in\mathbb{R}^{n\times n}$ with positive entries and zero diagonal, is it always possible to construct a high-dimensional configuration in Euclidean space, such that these ...
-1
votes
3answers
159 views

How to solve numerically such system of equations

I have a system of equations $$ S_{m}(\xi) +P_{m}(\xi)=f(\xi) $$ where $\xi$ can be choosen arbitrary in some domain in $\mathbb{C}$, $f$ is known, $P_m$ is a polynomial of degree at most $m$. ...
6
votes
1answer
175 views

Identifying the name/provenance of a technique to find the nullspace vectors of a matrix by random sampling and the conjugate residual method

I have got a large sparse matrix $A \in \mathbb R^{n \times n}$ and I want to find non-trivial elements in the kernel/nullspace of this matrix. How can this be done? I would like to learn more about a ...
2
votes
1answer
143 views

Factor a non-symmetric matrix into the product of a sparse symmetric matrix and a diagonal matrix plus a low rank correction

I have a non-symmetric matrix, where the non-symmetry only appears at a subset of points. This arises due to the particular manner on which boundary conditions are applied in a Cartesian grid method. ...
3
votes
2answers
226 views

How to efficiently compute the total least squares with an inequality constraint

I am looking for an efficient method to compute $$\sum_{i=1}^\left|B\right|\left|Ax_i-b_i\right|^2\rightarrow min$$ under the condition $$\forall i, x_i\ge 0,$$ where $A$ is an n-by-m matrix and $B$ ...
3
votes
2answers
263 views

Positive semi-definiteness of a (symmetric) matrix

Suppose a matrix $A\in\mathbb{R}^{n\times n}$ is given. Faced with a proof for $$x^TAx>0,$$ for a non-zero vector $x\in\mathbb{R}^{n}$, I was thinking to use the information of the spectrum of $A$ (...
2
votes
2answers
157 views

Handling inconsistent solutions obtained by PCA

In order to achieve a 2D representation $X\in\mathbb{R}^{n\times 2}$ of some high-dimensional data residing in $Y\in\mathbb{R}^{n\times k}$, I use PCA:$$X=Y\cdot U,$$where $U\in\mathbb{R}^{k\times 2}$ ...
7
votes
2answers
942 views

Can all eigenvalues of a Hermitian Toeplitz matrix be computed in $\tilde{O}(n)$ time?

I know there are "superfast" $O(n \log^p n)$ algorithms for solving Toeplitz linear systems. Is it possible to compute all eigenvalues of such a matrix with the same complexity?
1
vote
1answer
86 views

Normalizing axes prior to PCA

For a given centered configuration of points $X\in\mathbb{R}^{n\times 3}$, the covariance matrix is denoted by $S=\frac{1}{n}X^TX$. Recall that the 2D PCA solution is obtained by $Y=X\cdot U$, where $...
0
votes
1answer
74 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 ...
11
votes
2answers
3k views

Eigenvalue decomposition of the sum: A (symmetric) + D (diagonal)

Suppose $A$ is a real symmetric matrix and its eigenvalue decomposition $V \Lambda V^T$ is given. It is easy to see what happens with the eigenvalues of the sum $A + cI$ where $c$ is a scalar constant ...
1
vote
1answer
90 views

Debugging Shell matrix

I am trying to solve complex valued Poisson equation $$(C + \nabla. D \nabla )u = f \text{ ;where C, D, u and f are complex numbers.} $$ I am breaking this eqn into real valued problem, which is of ...
6
votes
3answers
528 views

How to solve a small least-squares problem

This question is not very deep. Suppose I have a small rectangular matrix $A$, with number of rows and columns between $50$-$100$, respectively. Given a right-hand side $b$, I want to solve the least-...
3
votes
3answers
3k views

Inverse of a 10X10 antisymmetric matrix

I want to invert a 10X10 antisymmetric matrix in Python around 10,000 - 20,000 times. Is there a faster way to do it other than to use the built-in inverse function in Python? Thanks.
2
votes
2answers
2k 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
287 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 ...
1
vote
2answers
170 views

Sparse non-square system of linear equations in exact arithmetic [closed]

What is the best known algorithm for exactly solving a large sparse system of linear equations? The system I'm working on is not symmetric, not positive definite and integer. The only benefit is being ...
4
votes
3answers
1k views

Spectrum of the product of two matrices

Given SPD matrix $$A \in \mathbb{R}^{N \times N} $$ and positive diagonal matrix $$D \in \mathbb{R}^{N\times N}.$$ What is then spectrum of the product $$D^TAD.$$ Is there a closed-form relationship ...
1
vote
2answers
5k views

BLAS/LAPACK subroutine to add two matrices with different offsets and leading dimensions

I currently searching for a subroutine from BLAS or LAPACK which realizes the following operation A = alpha*A + beta * B where A and B have different leading ...
10
votes
2answers
783 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 ...
8
votes
2answers
4k views

Updatable SVD implementation in Python, C, or Fortran?

I would like to do evolving factor analysis using the SVD: Given $m \times n$ data matrix $\mathcal{A}$, and for each $i$ from 1 to $m$, I want to calculate the singular values of: $$\mathcal{A}\...
6
votes
2answers
6k views

Recommendations for a usable, fast Java matrix library?

This complements an earlier question on usable, fast C++ matrix libraries. I've looked at the Java Matrix Benchmark, and it seems like the performance of java matrix libraries is all over the place. ...
7
votes
1answer
693 views

C library - iterative sparse complex linear equation solver?

Where can I find a library to solve a sparse complex matrix equation iteratively in C. So far I've only found libraries for direct solution to complex systems, and libraries for iterative solutions to ...
4
votes
2answers
3k views

What is the most efficient way to diagonalize small matrices?

I have a problem where I need to diagonalize a large number of small Hermitian matrices. Typically the matrices are between 4 and 64 in size (skewed towards the low end) and the number of matrices is ...
2
votes
0answers
668 views

Finding a permutation that makes a matrix lower triangular

I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
4
votes
3answers
1k views

Applications of Moore - Penrose generalized inverse of a matrix and associated projection?

I am seeking applications in the industry for the Moore-Penrose generalized inverse $A^\dagger$ of a matrix $A$. The Moore-Penrose Inverse of $A\in \mathbb{C}^{m\times n}$, denoted by $A^\dagger$, ...
2
votes
2answers
522 views

Exploring feasible points in a linearly defined space

What is the quickest way to find a point inside a linear feasible space? (Defined by the intersection of several hyperplanes and halfspaces). I want to be able to choose an initial point in the ...
14
votes
6answers
1k views

Approximate spectrum of a large matrix

I want to compute the spectrum (all the eigenvalues) of a large sparse matrix (hundreds of thousands of rows). This is hard. I am willing to settle for an approximation. Are there approximation ...
5
votes
1answer
2k views

eigenvalues (and determinant) of a hadamard product of matrices

I need to compute the determinant of a matrix that is calculated as $B \circ A$, with $B$ and $A$ being square matrices and $\circ$ representing their Hadamard product. One way of doing this is ...
13
votes
3answers
1k views

SVD for finding the largest eigenvalue of a 50x50 matrix -- am I wasting significant amounts of time?

I've got a program that computes the largest eigenvalue of many real symmetric 50x50 matrices by performing singular-value decompositions on all of them. The SVD is a bottleneck in the program. Are ...
3
votes
2answers
315 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 ...
2
votes
1answer
78 views

Computing a sequence of row interchanges that realizes a given permutation matrix?

This question is aimed at cleaning up an implementation detail of an in-house sparse direct solver. It uses METIS to reorder $A$ into $PAP^{T}$ for reduced fill-in. Inside the $Lx=b$ and $L^{T}x=b$ ...
19
votes
2answers
9k views

Null-space of a rectangular dense matrix

Given a dense matrix $$A \in R^{m \times n}, m >> n; max(m) \approx 100000 $$ what is the best way to find its null-space basis within some tolerance $\epsilon$? Based on that basis can I then ...
9
votes
2answers
182 views

Predict runtimes for dense linear algebra

I would like to predict runtimes for dense linear algebra operations on a specific architecture using a specific library. I would like to learn a model that approximates the function $F_{op} \;::\; $...
5
votes
1answer
457 views

Intersection of hyperplanes

A very basic question but i couldn't find another post about it: Given $p$ non parallel hyper-plane in $\mathbb{R}^p$: $\left(\begin{array}{cccc} c_{11} & a_{11} & .... & a_{1p} \\ ... &...
8
votes
1answer
358 views

Is the sparsity pattern of a linear system important for iterative (KSP) solvers?

Pretty much the question. Given a general sparse, non-symmetric (both numerically and structurally) matrix, how important is the sparsity pattern (i.e. row/column permutation of matrix/vector) for ...
9
votes
1answer
417 views

Solving a system with a small rank diagonal update

Suppose I have the original large, sparse linear system: $A\textbf{x}_0=\textbf{b}_0$. Now, I do not have $A^{-1}$ as A is too large to factor or any sort of decomposition of $A$, but assume that I ...
7
votes
3answers
782 views

Solving shifted linear systems with LU factorization

I am interested in solving a sequence of shifted linear systems $(A+\sigma I)x = b$ for various values of $\sigma$. The matrix $A$ is sparse and not too large, so I have its LU factorization available....
6
votes
2answers
282 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 ...
8
votes
3answers
419 views

What is too big for standard linear algebra/optimization methods?

Different numerical linear algebra and numerical optimization methods have different size regimes where they're a 'good idea', in addition to their own properties. For example, for very large ...
6
votes
2answers
546 views

Large-scale generalized eigenvalue problem with low rank LHS matrix

Assume that we have generalized eigenvalue problem: $B^HB\textbf{x} = \lambda A\textbf{x}$ where $A$ is an nxn Hermitian sparse matrix (n is very large, so we do not have $A^{-1}$ but can solve ...
6
votes
3answers
455 views

Multiply Multiple Sparse Matrices

When we calculate products of multiple matrices, e.g., $ABC$, do you think it can be done in a cheaper way than as two consecutive multiplications? Note that I'm not talking about applying matrices to ...
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.$$ ...
4
votes
1answer
127 views

Efficient computation of the extension of a linear basis to completion when the basis is almost complete (ideally using LAPACK routines)

I have a $p \times n$ matrix $B$ (where $n < p$) with orthonormal columns and would like to find a numerically efficient way to extend this matrix to get a complete $p$-dimensional orthonormal ...