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,109
questions
0
votes
1
answer
42
views
How do you build a polyharmonic discrete system?
Polyharmonic equations, to my understanding, are defined as:
$$\Delta ^k u = 0$$
i.e. one repeatedly applies the laplace operator to the function a certain number of times and the result must be 0.
...
- 263
4
votes
1
answer
89
views
Numerical continuation of all eigenvalues of small, dense matrices
Consider a one-parameter family of matrices $A(q)\in \mathbb{R}^{n\times n}$, $q\in\mathbb{R}$. For my applications, $n$ is typically between $5$ and $50$ and $A(q)$ is generally dense, so direct ...
- 1,832
0
votes
1
answer
74
views
+50
Computing discrete laplacian matrix for mesh fairing
I asked this question on the math stack exchange and got an answer, but I am just as utterly confused as before. My fundamental goal is to actually construct the matrix, that is, a series of steps I ...
- 263
37
votes
10
answers
8k
views
stupid + stupid = brilliant in scientific computing
I'm interested in examples of very effective methods in scientific computing that are the sum or naive combination of very ineffective or bad ones.
- 9,813
0
votes
0
answers
41
views
Different computational approaches to show that the conjecture is true
It seems that proving the statement given in the question https://math.stackexchange.com/questions/4601532/a-pen-and-paper-proof-for-a-matrix-implication is difficult analytically. I was thinking what ...
- 229
4
votes
1
answer
1k
views
Why are all eigen solvers iterative?
I have small dense square matrices for which I would like to compute the inverse by singular value decomposition, or equivalently solve the eigenvalue problem.
While there are many direct methods for ...
- 2,345
0
votes
1
answer
61
views
Solve bivariate polynomial system
Given a bivariate polynomial system with variables $(x, y, z)$ like
(1) $ f_1 = x * a_1 + y * a_2 + z * a_3 = 0 $
(2) $ f_2 = x * a_4 + y * a_5 + z * a_6 = 0$
(3) $ f_3 = x^2 + y^2 - 1 = 0$
how do I ...
- 11
8
votes
0
answers
266
views
Stable alternatives to "condition number"?
A number of numerical problems are easy to solve when condition number $\kappa$ of the problem is low. For instance, conjugate gradient descent complexity scales as $O(\sqrt{\kappa})$.
However
"...
- 2,049
3
votes
1
answer
55
views
Matrices that achieve worst-case $LDL^T$ element growth
Matrices that achieve the worst case $\rho_n = 2^{n-1}$ element growth in LU factorization with partial pivoting are known; see e.g. Theorem 9.7 in
Higham, Nicholas J., Accuracy and stability of ...
- 10.6k
0
votes
0
answers
42
views
How do compute lowest eigenvalue using Arpack in C language
Hi I have a problem to calculate lowest eigenvalue in non-symmetric matrix using Arpack, because my matrix is very complicated and even I have a lot of trouble to made a matrix - vector multiplication....
1
vote
0
answers
29
views
How to find the formula of a projected circle in a pencil of conics structure?
Hi this is my first question on the platform so feel free to comment if I have a mistake regarding the question.
I'm working on an ellipse detection scheme in which I have markers consisted of 3 ...
5
votes
1
answer
121
views
Estimating the sum of 4th powers of singular values?
Suppose $A$ is an $m\times n$ matrix with $\operatorname{Tr}(AA^T)=1$. Let $\sigma_i$ be the vector of singular values of $A$. How would I cheaply estimate the following quantity?
$$\rho(A)=\sum_i \...
- 2,049
3
votes
0
answers
80
views
When would one choose un-pivoted $LDL^T$ instead of $LL^T$ for a Positive Definite Matrix?
Background
I am decomposing (and then operating on) a symmetric positive definite matrix (a covariance matrix) as part of a larger system. Dimensions range from O(10) to O(300). The covariance ...
- 792
1
vote
0
answers
65
views
Optimal Krylov subspace dimension and iteration limits for eigs
When using the eigs function in MATLAB, which is based off of ARPACK, one can manually modify the maximal dimension of the constructed Krylov subspaces, the maximum iteration counts, and the error ...
- 43
2
votes
1
answer
75
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 ...
- 121
1
vote
0
answers
63
views
min(f(x)) is convex or concave based on type of f(x)
i have f(x) that is concave function. My question is g=min(f(x)) is concave or convex? And max(g) is concave or convex? there is a theorem for this?
- 11
2
votes
1
answer
137
views
Measuring the extent to which two sets of vectors span the same space
I have a set of measurements $y_i$, $1 \leq i \leq N$, and I want to model these measurements with a linear model. I have two possible models I can use,
$$
y \approx A c
$$
and
$$
y \approx B d
$$
...
- 1,038
3
votes
1
answer
171
views
Generalized eigenvalue problem for large, potentially ill-conditioned systems
Say that I have a generalized eigenvalue problem of the form $$Ax=\lambda Bx.$$ Using MATLAB, some naive ways that one may solve this is by either
directly inverting $B$ then applying the ...
- 43
1
vote
0
answers
63
views
How to show that the solution of the following quadratic programming is non-negative
I have the following quadratic problem:
$max$ $a^Tx+0.5x^TAx$
$s.t: 1^Tx=1$
in which $a=[a_1, a_2,...,a_n]$ is a non-negative vector, and $1^T=[1,1, ..., 1]$. The hessian matrix $A$ has the ...
- 11
11
votes
1
answer
979
views
Is using iterative methods to solve a linear system always superior to inversing the matrix?
I have a silly question. Is it always more computationally efficient to use iterative methods to solve for some matrix $A$, $Ax=b$, where $x$ and $b$ change but $A$ stays constant, compared to ...
- 121
2
votes
0
answers
61
views
When is Lanczos tridiagonalization accurate?
Suppose that we are given a random, symmetric matrix $A$, and a random vector $q$. For concreteness, assume the dimensions of $q$ and $A$ are both $1,000$. I would like to use the Lanczos algorithm to ...
- 41
1
vote
0
answers
45
views
Interpreting iterative smoothers and solvers as krylov preconditioners
Various literature and library implementations like petsc use preconditioners based on simple smoothers that themselves could be used the solve the systems directly. e.g. say I have a function
...
- 2,345
-1
votes
1
answer
26
views
How to generate p Sample of GGM of dimension m, for parameter : the weight, the means and the covariance?
after searching in the python numpy, scipy and sklearn module, there is no function who can generate p samples of a gmm (gaussian mixture model) for parameter means, covariances and the weight of each ...
- 1
1
vote
1
answer
111
views
QR algorithm for eigenvalues and eigenvectors of large symmetric matrices
I am trying to write a QR algorithm in Python for eigenvectors and eigenvalues finding for large symmetric matrices,
My initial thought was to use Householder transformation with a Wilkinson shift on ...
- 11
2
votes
1
answer
166
views
Numerically stable way to implement Cramer's rule analog
Problem statement
Let $A$ be an $n\times n$ matrix and $b$ an $n$-dimensional vector. For $j\in \{1, \dots, n \}$, let $A_j$ be the matrix where we take $A$ and replace the $j^{\rm th}$ column with $b$...
- 31
0
votes
0
answers
52
views
Rank-one updates for symmetric matrix eigen-system
Are there existing implementations for rank-one updating of symmetric matrices eigensystems?
This is the mathematical statement of the problem. Let $S=QDQ^T$
$$S + vv^T = QDQ^T +vv^T = Q_{new}D_{new}...
0
votes
1
answer
53
views
The row loss gradients
Suppose the original loss function is
$$\min_{\mathbf{V}}\frac{1}{2}\|\mathbf{V} - Q(\mathbf{V})\odot\mathbf{U}\mathbf{E} - \beta Q(\mathbf{V})\mathbf{V}\|_2^2$$
where $\odot$ denotes the element-wise ...
- 55
0
votes
1
answer
72
views
Compute a series of matrix multiplications and matrix norms quickly in Python
I need to compute a series of matrix multiplications involving 3x3 matrices and a series of matrix norms also involving 3x3 matrices and I wonder how I can set these computations up with numpy such ...
- 121
7
votes
1
answer
219
views
Eigenvalues of a $d\times d$ diagonal+rank1 matrix in $O(d)$ time?
Suppose $h$ is a vector of $d$ positive numbers adding up to 1. I'm looking for a $O(d)$ algorithm to estimate eigenvalues of the following diagonal + rank1 matrix:
$$A=2\operatorname{diag}(h)-hh^T$$
...
- 2,049
0
votes
0
answers
32
views
Matrix for Marker and Cell grid?
I have an assignment question that reads:
Show that the combined matrix for the Marker and Cell (MAC) grid
for velocity and pressure for the steady Stokes equations is symmetric.
You can consider the ...
- 263
2
votes
1
answer
171
views
Solution of linear system doesn't work, in parallel
I'm solving $Ax = b$ with PETSc, $A$ sparse and asymmetric.
I'm using BCGS or FGMRES or TFQMR as a solver, and ILU as a preconditioner.
When I use 1 core, everything works as expected. But with 8 ...
- 233
4
votes
1
answer
112
views
The error propagation in calculating the inverse using a matrix decomposition
I have been trying to calculate the matrix inverse of some large matrix with entries ranging by orders of magnitude. I tried to use the matrix decomposition to simplify the computation, where a matrix
...
2
votes
0
answers
96
views
Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?
Crossposted at MathOverflow
Consider a quadratic programming problem with the following format:
$$
\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\
$$
$$
\text{s.t.} Ax\leq b, \\
x\geq 0
$$
where $D$ is a $...
- 21
2
votes
0
answers
130
views
Does exact diagonalization of a matrix allow for efficient computation of a Lanczos basis?
Suppose that we are given a large, real-symmetric matrix $L$, which is simply too large to perform exact diagonalization on numerically. If we want to study its spectrum, one tool we can use is the ...
- 41
3
votes
1
answer
306
views
Time and memory required to diagonalize a 18000 by 18000 matrix using numpy in python
Can someone give an estimate of the Time and memory required to diagonalize a 20000 by 20000 complex hermitian matrix using numpy in python ?
- 31
4
votes
1
answer
115
views
Rank-1 correction of matrix exponential
I need to approximate the following in $O(d)$ time for $d\times d$ diagonal $A$ and rank-1 $B$
$$u^T \exp(-A+B) v$$
Here $u,v$ are vectors in $\mathbb{R^+}^d$, $A,B$ are positive semi-definite and $B$ ...
- 2,049
2
votes
0
answers
96
views
Schur complement formulation of linear system
Consider a system of the following form:
$$(A+K)x=b$$
where $A$ is symmetric, positive definite and block diagonal (in fact, a block diagonal matrix made of stiffness matrices arising from FEM ...
- 127
5
votes
1
answer
202
views
How to optimize an approximated matrix multiplication?
[UPDATING]
The old one is a simplified version of the current one. Here is a solution based on the answer proposed by professor Bangerth down below. To describe what I am trying to do, first rewrite ...
- 55
1
vote
1
answer
83
views
Powers of convergent DPR1 matrices in $O(d)$ time?
Suppose $u$,$v$ are vectors and $A$ is a convergent $d\times d$ diagonal + rank-1 matrix.
How do I estimate $u^T A^k v$ in $O(d)$ time?
Powers of convergent diagonal $D$ can be computed in $O(d)$ time ...
- 2,049
4
votes
2
answers
225
views
Faster than forward substitution?
I have a matrix of the form:
$M:=\begin{pmatrix}
S_1 & & & \\\ Q_1 & S_2 & & \\\ & ... & ... & \\\ & & Q_n & S_n\end{pmatrix}$
where the blocks ...
- 127
3
votes
0
answers
70
views
Approximating eigenvalues of DPR1 matrix with special properties
In my application, I have a sum of diagonal $A$ and rank-1 $B$
$$T=\underbrace{\text{diag}(1-2\alpha h+2\alpha^2 h^2)}_A + \underbrace{\alpha^2 hh^T}_B$$
Where $h$ is a vector $\in \mathbb{R}^d$ with ...
- 2,049
7
votes
1
answer
349
views
Computing powers of diagonal + rank-1 matrix?
I'm using a numeric root-finder to find $k$ satisfying $\|A^k x\|=c$ where $A$ is a symmetric $d\times d$ diagonal + rank-1 matrix. How to compute $A^k x$ efficiently?
For integer $k$, I can get the ...
- 2,049
0
votes
0
answers
56
views
Eigenvalues of same operator expressed in two different orthonormal basis are coming out different
I have an operator $H$. I express $H$ as a matrix in the orthonormalized $\{ |e > \}$ basis. Then I diagonalize it to obtain eigenvalues, let's say for example $H$ is $6 \times 6$ and the ...
- 31
2
votes
1
answer
93
views
Ways to fix block Lanczos tridiagonalisation numerical instability for matrix with degenerate, closely spaced eigenvalues?
I want to run a block Lanczos block-tridiagonalization on a hermitian, sparse matrix (of relatively small size $\sim 10^2 \times 10^2$). However the matrix typically has many eigenvalues that are ...
- 21
1
vote
1
answer
149
views
Lanczos memory complexity for dense matrices
Does the Lanczos algorithm remain memory efficient even if the original Hermitian matrix is dense?
- 11
1
vote
0
answers
61
views
Does the choice of a complex inner product affect Krylov methods?
As far as I understand there are two definitions of the complex inner product:
$$(a,b) = b^H a$$
and
$$(a,b) = a^H b$$
I know some linear algebra libraries such as BLAS and Eigen uses the second one.
...
1
vote
0
answers
43
views
FEM Basis for functions of two variables in $\mathbb{R}^2$ (Applied to Linear Full Stokes Equations)
I'm trying to do FEM for a very basic version of the linear full Stokes equations in two dimensions. Say we are working in the grid $[0,1]\times[0,1]$ in the $xy-$plane.
To solve an FEM problem for a ...
- 111
6
votes
1
answer
163
views
Inverse power iteration and solving singular system
The algorithm for the inverse power iteration works as following :
\begin{align}
&v^{(0)} =\text{ some vector with }\|v^{(0)}\|=1\\
&\text{for }k = 1, 2, \ldots\\
&\qquad\text{Solve } (A - ...
- 169
3
votes
0
answers
70
views
Householder Vector algorithm in Golub and Van Loan
(This is repost of a question first asked on Mathematics. Hopefully there are more people here who have a copy of Golub and Van Loan to hand)
In the 4th edition of "Matrix Computations", ...
- 181
2
votes
2
answers
191
views
How can I express the solution to a discrete Lyapunov equation as an eigenvalue problem?
Given the discrete Lyapunov equation $$AXA^T - X + Q = 0$$ how can I solve for $X$ as a function of the eigenvectors of some matrix $H$?
More precisely, in the case of the continuous Lyapunov equation ...
- 165