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
2 votes
0 answers
44 views

Inverses of many standard subspaces of one large matrix

i have a large rectangular invertible matrix M (about 5000x5000) and i have a loop in which i do the following for each iteration i (there are about 6000 iterations): i am given a subspace S_i (which ...
user avatar
  • 131
7 votes
0 answers
288 views

Implementation of Lanczos method that returns tridiagonal matrix

The Lanczos method can be used to obtain extremal eigenpairs of sparse symmetric or hermitian matrices. I know there are several implementations of the Lanczos method (as well as Arnoldi, Davidson, ...
user avatar
  • 171
1 vote
1 answer
302 views

Incomplete LU decomposition of sparse matrix

I have a sparse matrix stored in CSR format. For this matrix, I would like to get the incomplete LU decomposition. I tried to find algorithms which can utilize the CSR format but I could not find ...
user avatar
1 vote
1 answer
309 views

How to use QZ decomposition for single matrix in Matlab?

Can I use QZ decomposition on a single square matrix in Matlab? Like, [Aa,Q,Z]=qz(A);
user avatar
3 votes
3 answers
234 views

Fast iterative approximate order-oblivious Orthogonalization algorithm?

I have set of N m-dimensional vectors $\{\phi_i\}$ which gradually loses mutual orthogonality in an algorithm. => I have to re-orthogonalize them every few iterations. But if I use the Gram–Schmidt ...
user avatar
3 votes
1 answer
108 views

Why are the round-off errors when solving the linear system $Ax = b$ of order $\varepsilon_\text{mach} x_j$?

I was reading a paper on arXiv where, in Section 2.4, the authors are discussing the error that arises in the solution of a linear system $$Ax = b,$$ or, to match up better with the paper, $$\Phi \...
user avatar
  • 133
4 votes
1 answer
935 views

Is there a library that allows einstein summation on dense, sparse, and LinearOperator type tensors

Numpy's einsum only works with dense tensors. Is there an alternative that also works with sparse tensors and linear operators? For example, I might have a ...
user avatar
  • 717
3 votes
1 answer
229 views

Matrix condition number and reordering

Does the condition number change when a matrix is reordered by e.g. Cuthill Mckee or some other method?
user avatar
5 votes
0 answers
391 views

Is there any catch on using `zgemm3m` vs regular `zgemm`?

I've just (to my embarrassment) encountered a BLAS-like extension of a matrix-matrix product subroutine gemm in Intel MKL: gemm3m...
user avatar
  • 8,451
1 vote
1 answer
128 views

How to implement this even-odd matrix decomposition efficiently?

Note: This question has also been asked on stackoverflow - see https://stackoverflow.com/questions/57197910/how-to-implement-this-even-odd-matrix-decomposition-efficiently?noredirect=1#...
user avatar
1 vote
0 answers
59 views

Does Boost provide a template implementation of the wedge product?

Does the boost C++ library implement the computation of the wedge product? The wedge product is mentioned here, but it is not very clear (to me at least) whether there is a template implementation of ...
user avatar
1 vote
0 answers
81 views

What's the more efficient way to solve this matrix equation?

This is intended to be a more generic question not about a specific system. Given a hermitian matrix $H(x_1,\dots,x_n)$ depending non-linearly on some real parameters $x_1,\dots,x_n$. We want these to ...
user avatar
2 votes
1 answer
82 views

How to pass matrices to parallel workers quickly in matlab?

I am trying to solve many different linear systems in parallel in matlab. The problem is, each linear system has entirely different parts and are fairly large, so passing the information to each of ...
user avatar
1 vote
1 answer
171 views

Sparse matrix inversion

I have the impedance matrix $Y$, formulated from an electrical network by augmented nodal analysis. The matrix $Y$ is shown as an image to illustrate its feature visually, where all the white blocks ...
user avatar
2 votes
1 answer
98 views

numpy.outer without flatten

$x$ is an $N \times M$ matrix. $y$ is a $1 \times L$ vector. I want to return "outer product" between $x$ and $y$, let's call it $z$. z[n,m,l] = x[n,m] * y[l] ...
user avatar
  • 121
0 votes
1 answer
115 views

what does “D = diag(W.1)” means?

, what does “D = diag(W.1)” means?on page #2, just below equation (6) PFA screenshot and here is the link of the paper - original paper
user avatar
5 votes
1 answer
910 views

Fast algorithm for computing cofactor matrix

I wonder if there is a fast algorithm, say ($\mathcal O(n^3)$) for computing the cofactor matrix (or conjugate matrix) of an $N\times N$ square matrix. And yes, one could first compute its determinant ...
user avatar
  • 53
3 votes
1 answer
231 views

Null space for smoothed aggregation algebraic multigrid

I do not really get the point of null space usage for creating the prolongation operator for smoothed aggregation algebraic multigrid. I know what the null space is per definition and I know that the ...
user avatar
2 votes
0 answers
313 views

Regularized least squares with QR factorization

Consider the regularized least squares problem $$ \min_x || b - A x ||^2 + \lambda^2 ||x||^2 $$ which is equivalent to $$ \min_x \left|\left| \pmatrix{b \\ 0} - \pmatrix{A \\ \lambda I} x \right|\...
user avatar
  • 956
5 votes
1 answer
158 views

Complex differentiation of linear solvers

I have a linear system $$Ax=b$$ which I'm solving approximately, and I need to take the frechet derivative of x with respect to z. Were I solving the problem exactly (either analytically or to machine ...
user avatar
  • 1,902
3 votes
1 answer
264 views

Optimality of block-Jacobi preconditioner

For a dense $N \times N$ matrix $A$, is the block-Jacobi preconditioner comprising the inverse of the diagonal blocks of $A$ the optimal block-diagonal preconditioner? Could there exist another matrix ...
user avatar
  • 653
1 vote
0 answers
70 views

Kinetic preconditioning

Publication arXiv:0804.2583 describes a method for doing self-consistent iteration without having to diagonalize the Hamiltonian operator at every step. IX. PRECONDITIONING As already mentioned, ...
user avatar
  • 331
0 votes
0 answers
46 views

A preconditioner for self-consistent iteration

I tried to derive a preconditioner for self-consistent iteration similar to section IX in arXiv:0804.2583. For simplicity, consider here only one orbital (one or two electrons) systems. Suppose that ...
user avatar
  • 331
3 votes
1 answer
245 views

Whitening transformation does NOT return a unit covariance matrix

For this question, I am using the following Wiki definition of Matrix whitening: Suppose $X$ is a random (column) vector with non-singular covariance matrix $\Sigma$ and mean 0. Then the ...
user avatar
  • 133
2 votes
1 answer
154 views

In iterative methods, are matrix decompositions considered useful for implementation?

When we study an iterative method from textbooks, for example, see the Gauss-Seidel Method, the given matrix is decomposed with suitable splittings. In the example, $A = L+U$. So we can proceed with ...
user avatar
  • 137
5 votes
2 answers
477 views

Python: vectorizing a structured linear system solve

Overview I am looking for a way to solve a structured linear system in Python without using a for loop (preferably using vectorization, if possible). Background Consider the following linear system:...
user avatar
2 votes
1 answer
344 views

Re-using LU factorization within iterative (?) setup for a sum of two matrices

So, I would love to make at least some use of my preexisting data, no matter how small, and just out of ideas. Maybe I am just a prisoner of a Kahneman-like theatre-ticket paradox, and don't know ...
user avatar
  • 8,451
4 votes
1 answer
389 views

Accurate way of getting the square root inverse of a positive definite symmetric matrix

What is the most accurate algorithm to get the square root inverse of a positive definite symmetric matrix? I am not looking as much for efficiency, though using quadruple precision computation is out ...
user avatar
4 votes
2 answers
453 views

Compiled c++ code runs much faster with double than float. Explanation?

I am still rather new on here and I hope question is suitable for this forum otherwise please help me migrate it to greener pastures. I am an electrical engineer specializing in applying mathematics ...
user avatar
5 votes
1 answer
546 views

CHOLMOD condition number estimate

The CHOLMOD library provides a CHOLMOD_rcond function that estimates the reciprocal condition number (in the one norm) of a symmetric positive definite matrix from ...
user avatar
  • 241
4 votes
2 answers
92 views

How to efficiently invert $K \otimes M+I_T\otimes \Sigma$?

I'm looking for a way to efficiently invert $$K \otimes M+I_T\otimes \Sigma$$ where the inverses for $M,K$ exist. $I_T$ is the identity matrix of dimension $T$, and $\Sigma$ is a diagonal matrix, with ...
user avatar
2 votes
1 answer
53 views

Discretization with non-constant matrix containg entries form unknown vector

Consider a system of PDEs $$ \begin{cases} u_t = \nabla \cdot (D(u)\nabla u) + \frac{c}{K_U+c}u-ku\\ c_t = d_c\Delta c -\frac{\nu_U c}{K_U + c}u \end{cases} $$ with some boundary conditions. Here, $D(...
user avatar
  • 216
40 votes
23 answers
10k views

Good examples of "two is easy, three is hard" in computational sciences

I recently encountered a formulation of the meta-phenomenon: "two is easy, three is hard" (phrased this way by Federico Poloni), which can be described, as follows: When a certain problem is ...
user avatar
  • 8,451
1 vote
0 answers
65 views

Stability of SVD, Eigendecompositions, and pseudoinverse procedures in modern LAPACK routines

I have proposed an optimisation algorithm which I claim has improved upon the previous algorithm in a number of ways. One of these claims is that my proposed solution requires no explicit SVD and ...
user avatar
2 votes
1 answer
93 views

How to add extra constraints to a linear system for probabilities?

Background: I have an equation which looks like as follows: $W \times P = R$ $$\left[\begin{array} &{1}&{0}&{0}&-\frac{w_{1}}{w_{o1}} &\dots &{0} &-\frac{w_{1}}{w_{0} } \...
user avatar
  • 123
2 votes
1 answer
195 views

Rank of Hadamard Product with Masked Matrix

I have a matrix $A\in\{0,1\}^{d\times n}$ and $rank(A)=d,d<n$, and another matrix $X\in \mathbb{R}^{d\times n}$, but I do not know the rank of $X$. What can we say about the rank of their Hadamard ...
user avatar
  • 89
2 votes
1 answer
248 views

How to compute the determinant of Hessian of a multivariable function?

I have a function $F(\vec x)$ of many variables (let's say in the order of hundreds of thousands). I need to compute the determinant of the Hessian matrix at the point $x_0$. Is there a way to ...
user avatar
  • 151
3 votes
2 answers
938 views

Convexity of Sum of $k$-smallest Eigenvalue

If I have a real positive definite matrix $A\in\mathbb{R}^{n\times n}$, and denote its eigenvalues as $\lambda_1\leq \lambda_2 \leq ... \leq \lambda_n $. Define the function as $f(A)=\sum_{i=1}^{k} \...
user avatar
  • 89
0 votes
1 answer
59 views

An Upper Bound of $\left<H,X\right>_F$ with Constrainted Rank

We have $X=[\mathbf{x}_1,\mathbf{x}_2...,\mathbf{x}_n]\in\mathbb{R}^{d\times n}$, $H=[\mathbf{h}_1,\mathbf{h}_2...,\mathbf{h}_n] \in\mathbb{R}^{d\times n}$, and $d<n$. $H$ has rank $r\leq d$ and $X$...
user avatar
  • 89
2 votes
1 answer
102 views

Which pseudo-inverse to compute when Inverse is not possible? (No linear solve)

Let us assume that we have a function, $f(A)=\text{vec}(A^{-1})^\intercal B$, dependent on $A^{-1}$. However, due to some machine-precision limitations, the programming language I'm using cannot ...
user avatar
5 votes
2 answers
255 views

Computing any element of the null space of a singular matrix

Given a singular matrix $A$, what is the fastest method to find a single non-zero solution to $Ax=0$? Note that we are not looking for the whole kernel, we just want any non-zero vector in it. I ...
user avatar
3 votes
1 answer
3k views

A fast way to check if a Matrix is ill-conditioned, and turning it into well-conditioned

I'm running a simulation, and some linear solvers are returning a message of ill-conditioned matrix. Hence, I'm looking for a fast, easy to implement, method to detect if a matrix is ill-conditioned, ...
user avatar
4 votes
1 answer
57 views

Determine image of hypercube under linear map

Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
user avatar
1 vote
0 answers
106 views

Connection between piecewise linear basis functions and RELU activation function

ReLU activation is defined as follows $$\sigma(x)=\max(0, x).$$ Let's assume that I have deep network of 1 hidden layer, than output from my layer has form $$ f(x)= \sigma(Wx +b), $$ where matrix W ...
user avatar
1 vote
1 answer
346 views

Gaussian Elimination Using Fortran [closed]

I developed the code below for performing gaussian elimination in order to evaluate the determinant of a matrix: ...
user avatar
  • 11
1 vote
1 answer
84 views

Product of rank one updates as a low rank update for quasi newton/BFGS

I'm trying to improve the speed of the following iteration to calculate $s_k$: $$B_k^{-1} = \Bigg( I + \frac{s_{k}s_{k-1}^T}{||s_{k-1}||^2}\Bigg)...\Bigg(I+ \frac{s_1s_0^T}{||s_0||^2}\Bigg) B_0^{-1}\\...
user avatar
  • 11
9 votes
4 answers
1k views

fastest linear system solve for small square matrices (10x10)

I am very interested in optimizing the hell out of linear system solving for small matrices (10x10), sometimes called tiny matrices. Is there a ready solution for this? The matrix can be assumed ...
user avatar
  • 129
0 votes
1 answer
66 views

Finding Matrix inverse with LU and repeted left division calls

Hello I am in a basic numerical methods class and our teacher has given us an algorithm which can compute the inverse of a matrix other than using MATLAB's built in library function. ...
user avatar
  • 101
5 votes
3 answers
152 views

Finding exact rational solution to linear integer equations in Matlab

I have a linear system of equations $$Ax=b$$ where $A$ is an $N\times N$ matrix with integer values, and $b$ is a $N\times 1$ vector with integer values. Due to prior knowledge, I know that I am ...
user avatar
6 votes
1 answer
125 views

numerical solution of an under-determined linear equation in high dimensions

I need to solve a linear regression problem $$Ax=y$$ which is hugely underdetermined. I have around $10^6$ features but only $10^3$ equations. So $A$ is a $1,000\times 1,000,000$ matrix and $y$ a ...
user avatar
  • 247

1
3 4
5
6 7
22