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.
1,053
questions
2
votes
1
answer
120
views
Efficient change of basis real positive definite symmetric matrix
I need to optimize a code where the most performance critical part is doing a 'change of basis', in other words it is an unitary similarity transformation on a big real positive definite symmetric ...
0
votes
0
answers
126
views
Ill-conditioned stiffness matrix
I am writting a Fem code in c++ for a 2d plane stress model. My question is regarding the assembly stiffness matrix.I noticed that some elements of the matrix are not exactly zero but insted a number ...
- 471
1
vote
1
answer
121
views
Jacobi iterative method
I'm using Jacobi iterative method for finding eigenvalue and eigenvector for hermitian or symmetric matrix. Eigenvectors corresponding to eigenvalues are not exact. The third eigenvector is totally ...
- 11
1
vote
0
answers
25
views
Multiplying by E[xy'] where only some statistics of xy' are known
(cross-posted on crossvalidated)
For random variable $(x,y)$ in $\mathbb{R}^{d}\times \mathbb{R}^{d}$ and vector $v \in \mathbb{R}^d$, I need to perform the following matrix vector multiplication.
$$T(...
- 1,442
5
votes
0
answers
172
views
Inverse problem with uncertain forward operator
Suppose I want to solve a linear inverse problem. In this example we take a convolution with the kernel:
$$\frac{1}{(y^2+z^2)^{3/2}}$$
We only take a fixed $z$ for the computation and convolve with ...
- 720
7
votes
2
answers
2k
views
When is it easy to invert a sparse matrix?
(Crossposted on cstheory.SE)
When is it easy to invert a sparse matrix? Specifically, I'm wondering about the cases in which matrix inversion has similar cost to sparse matrix multiplication, hence ...
- 1,442
2
votes
1
answer
48
views
Solving MX=N where M is structured as a Gaussian 4th-moment tensor
I'm looking to solve numerically the following equation for $(d,d)$ variable $X$, in Einstein summation notation
$$M_{ijkl}X_{kl}=N_{ij}$$
Where $M$ is a $(d,d,d,d)$ 4th-moment tensor of random ...
- 1,442
2
votes
1
answer
281
views
Ill-condioned Linear System and Gaussian Elimination
Suppose that I have a linear system $Ax=b$ such that $A$ is ill-conditioned. Can I say that it is dangerous to find a solution with Gaussian Elimination for this system, or does there exist some class ...
- 21
3
votes
2
answers
288
views
1D FEM for nonlinear diffusion coefficient
I want to solve with linear finite elements the equation $$\partial_t u = \partial_{x}(a(u)\partial_xu)$$
in the domain $t \in [0,1]$ and $x \in [-L,L]$. Here $a(u)$ is just a function of $u$.
...
- 289
3
votes
1
answer
111
views
Efficient solution to a structured symmetric linear system with condition number estimation
I have a real-valued linear system $Hx = b$ where $H$ is symmetric matrix** (not necessarily positive/negative definite) with a very particular structure:
$$
H = \begin{bmatrix} D && B \\ B^T &...
- 752
0
votes
0
answers
47
views
Norm estimates if adjoints can't be computed
Assume that you have two linear maps $A$ and $V$. For a given $x$ (of appropriate dimension) you can compute $Ax$ numerically, and for any $y$ (of appropriate dimension) you can calculate $V^Ty$ ...
- 1,728
6
votes
1
answer
875
views
Cheap recalculation of eigenvalues and eigenvectors for a low-rank update of the matrix
Suppose I have a correlation matrix, $A$, and I already have the eigenvalues and eigenvectors of this matrix.
For a given vector, $\mathbf{\mathit{v}}$, I want to calculate the eigenvalues and ...
- 179
2
votes
1
answer
1k
views
Runtime of Gaussian elimination/row reduction on a rectangular $m \times n$ matrix
The runtime of Gaussian elimination on an $n \times n$ matrix is $O(n^3)$. What is the runtime on an $m \times n$ matrix?
I am taking Gaussian elimination to mean putting the matrix in reduced row ...
- 23
1
vote
1
answer
155
views
Frobenius norm of a binary matrix
In term of the mathematical distance measurement,
What is the significance of a Frobenius norm for a binary matrix?
- 31
1
vote
1
answer
260
views
How to optimize nuclear norm subject to positive semidefinite constraints?
For finite dimensional symmetric positive semidefinite matrices $A$ and $B$, I would like to solve
\begin{align}&\min |X - A|_1 \\
&\text{subject to}\\
&X \preceq B \\
&0 \preceq X\...
- 113
0
votes
0
answers
79
views
Derivative-free ill-conditioned non-linear least squares
I am looking for a package which can solve (non-linear) least squares problems without the use of derivatives (because of an expensive model), but which also deals with ill-conditioning well (such as ...
- 131
9
votes
4
answers
727
views
Checking singularity of a matrix
Suppose that we don't know $n \times n$ matrix $A$ explicitly but we are only able to compute products $Ax$ where $x$ is a column vector with $n$ elements. Is there an algorithm to determine whether $...
- 331
1
vote
3
answers
383
views
How to determine global stiffness matrix is constrained or not
Background
In solid fem, we often solve $$\mathbf{Ku}=\mathbf{p}$$
where $\mathbf{K}$ is global stiffness matrix, $\mathbf{u}$ is displacement, $\mathbf{p}$ is global load vector.
If displacement not ...
- 323
2
votes
1
answer
171
views
Efficient projection of a vector onto matrix kernel
Given an $m \times n$ matrix $A$ and a vector $x\in\mathbb R^n$, with $m<n$, what's an efficient way of computing the projection of $x$ onto the kernel of $A$?
- 1,629
7
votes
2
answers
401
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 "...
- 213
2
votes
2
answers
683
views
Solution of the linear system using Sherman-Morrison formula for 1000000x1000000 (7450.6GB) matrix using MATLAB
Let $n = 10^6.$ Let $A \in \mathbb{R}^{n\times n} $ be the lower triangular matrix having 1's on and below the main diagonal.
We want to solve the following linear system:
$$ (A + uv^T)x = b$$
by the ...
user36184
3
votes
0
answers
427
views
Compute Nullspace of Sparse Matrix
I am computing the nullspace of a sparse rectangular $m$ x $n$ matrix $A$, where $m$ << $n$. I do this by computing the QR decomposition of $A^T$ and extract the $n-m$ right-most columns of the ...
- 576
3
votes
0
answers
82
views
Numerical calculation of the Berry connection
I'm doing some numerical calculations involving Hermitian matrices, and derivatives of the eigenvectors.
Essentially, I have an n x n, Hermitian matrix H(x), which is dependent on some continuous ...
3
votes
0
answers
93
views
Is the matrix exponential and the Jordan canonical form actually useful for solving differential equations?
All of my yearlong graduate-level Linear Algebra course notes from my professor—an algebraist/representation theorist—shows his love for the exponential map $e^A$ and the Jordan canonical form—and one ...
- 31
5
votes
1
answer
154
views
Accurately Computing a Positive Vector in the Nullspace of a Matrix
I'm sure this question has been asked before yet after many hours of searching I am unable to find a definitive answer.
The problem at hand is solving the linear system: $$A \mathbf{x} = \mathbf{0}$$ ...
- 53
0
votes
0
answers
194
views
A parallelized GMRES solver?
My application calls for solving a dense, 40,000 x 40,000, ill-conditioned linear system. The native SciPy GMRES solver with preconditioning has worked well for my application and solving a single ...
2
votes
0
answers
90
views
Why is LAPACK (seemingly) suboptimal for packed and banded eigenvalue problems?
Based on this LAPACK routines list, it looks like there is no relatively robust representation (RRR) driver routine for either packed or banded symmetric eigenvalue problems. According to the relevant ...
- 191
7
votes
3
answers
414
views
Is LAPACK behind the cutting edge of dense linear algebra?
I have been digging into some numerical linear algebra lately, and reading in particular about how LAPACK solves symmetric eigenvalue problems. I noticed that the ...
- 191
1
vote
2
answers
326
views
Why OpenFOAM uses its own data structures and linear solvers?
I wonder why OpenFOAM code has its own data structures Lists, HashTables, ... etc. when there is the STL in C++?
Another ...
2
votes
1
answer
92
views
Parallel, matrix-free estimate of the trace
What would be the best way to estimate the trace of a large, distributed matrix, if one only know its action on a vector throug a parallel "matvec" routine?
In the application I am interested in, the ...
1
vote
0
answers
45
views
Triangle on top of diagonal least squares
I need to solve many least squares problems with the following matrices:
$$
\pmatrix{ R \\ D_i }
$$
where $R$ is upper triangular and $D_i$ is diagonal. $R$ is the same for all the problems, while $...
- 956
2
votes
1
answer
368
views
Boundary conditions in a finite element eigenvalue problem
I've been reading multiple papers and related posts for a while now, but I can't seem to find a specific answer to the issues I'm having so I hope someone can clarify things here.
I'll provide some ...
- 23
3
votes
1
answer
215
views
Implementation of a $O(n \log(n))$ method to compute eigenvalues of real symmetric tridiagonal matrices
I just came upon this paper, which details the implementation of a fast method to get eigenvalues of tridiagonal symmetric matrices :
Coakley, Ed S.; Rokhlin, Vladimir, A fast divide-and-conquer ...
- 153
1
vote
1
answer
199
views
Solving triangular matrix equations on a GPU
Suppose I have these two $N\times N$ lower triangular banded matrices:
$A = \begin{bmatrix}
a_0 & & \\
a_1 & a_0 & \\
a_2 & a_1 & a_0 \\
a_3 & a_2 & a_1 & a_0 \\
&...
- 771
1
vote
1
answer
58
views
Norm of operator in finite element discretization of Heat equation
I am solving the heat equation discretized spatially via FEM and temporally via backward Euler.
I get the system
$$M \dot{u} = K u +f$$ where $u$ is a vector representing the solution at spatial ...
- 145
1
vote
0
answers
43
views
Choosing the pivot for the rotation matrix in similarity transformation
I have arrived at an equation in the similarity transformation -
$M_r$ = $T. M_{r-1}. T^t$ ,where $T$ is the rotation matrix and $M_r$ ,$M_{r-1}$ are similar matrices. My aim is to find the rotation ...
- 11
4
votes
0
answers
445
views
Fastest matrix library for Android (with GPU is possible)
I was working on an Android app that requires some linear algebra with matrices. The matrices will be somewhat medium-sized as they are not too small or too big. I was originally using jBlas because ...
2
votes
0
answers
41
views
Is there a published RQ decomposition column-major algorthm?
I am refactoring an existing algorithm where where a RQ decomposition (as opposed to the more common QR) would be rather useful.
Most common books on the subject (e.g. Golub and Van Loan) discuss QR ...
- 752
0
votes
0
answers
90
views
Is there a subfield within computational science research that's done on pencil and paper?
Is there an area of computational science research that can be done on pencil and paper (with results written up for a journal format later on)?
I'm wondering if there is abstract proof-based linear ...
-1
votes
1
answer
79
views
Find mass matrix in a system of linear equations
Given $z_t=\sum_{i=1}^t \theta_iz_{t-i}+v_t $, where $t=1,...,N$ where $N=1024$. I need to write this in matrix form (a system of linear equations) as $\mathsf{A}\mathsf{z} = \mathsf{z} - \mathsf{v}$. ...
- 101
1
vote
1
answer
89
views
Flops of the computation of symmetric matrix $A$ to the power of $p$
What is the cost in terms of flops for the computation of $A$ to the power of $p$, where $p$ is a positive integer and $A \in \mathbb R^{n\times n}$ is a symmetric matrix?
3
votes
3
answers
421
views
Using matrix exponential to solve linear system
Consider the system of linear equations:
$$
Ax=b
\tag{1}
\label{eq1}
$$
where
$A\in\mathbb F^{n\times n}$, diagonalizable dense matrix, over the field $\mathbb F$ of real or complex numbers,
$x\...
- 8,451
-1
votes
2
answers
292
views
How to solve system of equations with almost-zero determinant?
I have a system of equations that I am trying to solve. In matrix form, it's written as
$$x(I - S) = b.$$
I am solving for $x$, where $I$ is the identity matrix and $S$ is a matrix where each column ...
- 119
0
votes
1
answer
1k
views
Desmos saying there are too many variables [closed]
I wasn't sure if this is a Computational Science SE question or a Stack Overflow question but I think it's more of this one.
I wanted to make a graph where I can rotate a hyperbola (not parabola or ...
- 103
2
votes
3
answers
693
views
Generating Random Orthogonal Matrices in C++
I'm looking for an open-source library for the generation of random n-dimensional orthogonal matrices in C++.
In python, it looks like such a function is available in the NumPy package. But I was not ...
2
votes
1
answer
251
views
Sparse matrix-matrix multiplication using AVX2
I have two sparse general matrices stored in CSR format I need to multiply. Is there any chance to gain performance using AVX2? In general the matrices are big (hundreds of millions of non-zeros and ...
- 818
0
votes
1
answer
620
views
How to implement the Hessenberg QR Algorithm?
For context, I'm creating a linear algebra library from scratch for learning purposes in C. Right now I'm working on calculating eigenvalues but my implementation of the QR Algorithm is diverging. ...
9
votes
1
answer
2k
views
Increasing computational performance by using 16 bit numbers
I recently found the following article where it was stated that using 16 bit numbers can be used to increase the computational performance of AI applications. According to the article numbers above 16 ...
- 818
0
votes
2
answers
328
views
Update for QR factorization least squares
I found after some research that the most numerically stable way to solve the least squares problem is through QR factorization. For $n$ number of observations and $p$ number of parameters it takes ...
- 356
4
votes
2
answers
2k
views
Cholesky decomposition vs LDL decomposition
In different books and on Wikipedia, you can see mentions of Cholesky decomposition and only sometimes of LDL decomposition.
As far as I understand, LDL decomposition can be applied to a broader ...
- 356