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,124
questions
0
votes
0
answers
15
views
Help with inferring Network topology from Spectral templates
I am trying to use matlab and YALMIP to solve a graph learning problem of recovering eigenvalues from the eigenvectors of the covariance of sampled graph signal data. This is to implement the ...
1
vote
1
answer
43
views
Finding the Vector $v$ for a Given Householder Matrix Transformation of Non-Collinear Vectors $a$ and $b$
Consider a vector $v$ in $\mathbb{R}^{n\times1}$. The Householder matrix is defined as follows:
$$H(v)=I-\dfrac{2vv^T}{v^Tv}.$$
It can be demonstrated that $H(v)$ is symmetric and orthonormal. The ...
- 5,544
0
votes
1
answer
67
views
Are there any established direct eigensolvers for sparse hermitian matrices?
I have experience with LAPACK (direct solvers) and ARPACK (sparse iterative solvers), but are there any sparse direct solvers? I am concerned more with preserving space than with fast solutions. ...
- 54.2k
12
votes
2
answers
2k
views
Why are systems with clustered eigenvalues easy to solve?
I came across the following slide by Theo Diamandis & Zachary Frangella on what makes the linear system $Ax=b$ easy to solve using the conjugate gradient method.
Transcription:
CG converges ...
- 2,054
3
votes
1
answer
143
views
Estimating the spectral radius when applying the method of lines
Some time integrators, notably the Runge-Kutta-Chebyshev method, implemented in the RKC code from Sommeijer & Verwer, gives the user an option to provide a callback with an estimate of the ...
CommunityBot
- 1
2
votes
0
answers
42
views
How to use a preconditioner estimated from a subset of data?
Suppose I'm solving $Ax=b$ using row-action method like Kaczmarz for $m\times n$ matrix A with $m\approx \infty$ and have $H_k=\frac{1}{k}A_k^T A_k$ which is an estimate of the Hessian obtained from ...
- 2,273
3
votes
1
answer
184
views
Solving underdetermined Lyapunov equation?
I'm solving the following for $X$ with $A,B$ singular positive semidefinite matrices.
$$AX + XA = B$$
Because $A$, $B$ are singular, standard Lyapunov solver fails
However, if I heuristically skip ...
- 11.1k
2
votes
1
answer
82
views
enough conditions to check that a matrix doesn't have Cholesky factorization while factorizing it
I wrote this code to find Cholesky factorization of a symmetric positive definite matrix in MatLab:
...
- 2,411
0
votes
1
answer
179
views
Problems on the algebraic theory of sparse matrices
I have finished testing basic large densely parallel matrix multiplication on 4 gpu's ,and have done work on TSLU and TSQR on cpu's based on mpi. I am going to continue working on the theory of ...
3
votes
0
answers
112
views
Stochastic power iteration for generalized eigenvalue problems?
Suppose $\mathbf{x}$ is a random variable in $n$ dimensions, and $u$ is a vector. How can I estimate the following quantity in an online fashion?
$$f(x)=\max_{\|u\|=1} \frac{ E\left[\langle u\cdot x\...
- 2,273
0
votes
0
answers
16
views
How do you determine the Mott-Insulator to Superfluid transition in the Bose Hubbard System
I am doing some simulations on various systems expressed in 2nd quantization and one of the points of interest of mine was Phase transitions in the Bose-Hubbard model
$$
H = \sum_{k} \{ t_k(b^\dagger_{...
2
votes
1
answer
1k
views
Calculate partial trace of an outer product in Python?
I have a python implementation of calculating the partial trace over select dimensions.
...
- 101
1
vote
1
answer
61
views
Dyadic product of a Gaussian vector (in Convolution kernel)
I was reading about the 2D Gaussian-blur convolution kernel. A Gaussian vector is a vector where the elements follow a Gaussian distribution. In my case, the kernel is symmetric and hence we take a ...
- 933
10
votes
1
answer
3k
views
What is the state of the art algorithm for diagonalizing real symmetric matrices?
There are many methods for diagonalizing matrices, probably the most widely used is the combination of Householder transformations and the QR algorithm.
Is there any superior method for diagonalizing ...
- 109
4
votes
1
answer
300
views
How to efficient solve $e^{-tA} x =b$, where A is a very sparse matrix
I am going to solve an equation containing an exponential matrix $e^{tA} x =b$, which can be obtained naturally through $x=e^{-tA} b$. A is a 1million $\times$ 1 million matrix with stores 7.15 ...
- 1,271
0
votes
1
answer
257
views
Questions on the theory of distributed numerical algebraic computation
I'm trying to build a pure python distributed numerical algebra computation kernel based on GPU. but after I've learnt most of the software engineering, I realise that I'm seriously lacking in ...
- 750
0
votes
0
answers
45
views
recommendation on some papers/books about frontal solver used in FEM
I'm reading a program about computational plasticity, this program use frontal solver to solve the program, but I'm not familiar with frontal solver even after reading some papaers, so could you ...
- 151
16
votes
3
answers
16k
views
What is the fastest way to compute all eigenvalues of a very big and sparse adjacency matrix in python?
I'm trying to figure out if there is a faster way to compute all the eigenvalues and eigenvectors of a very big and sparse adjacency matrix than using scipy.sparse.linalg.eigsh As far as I know, this ...
- 10.1k
0
votes
1
answer
85
views
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 ...
- 1,271
4
votes
1
answer
99
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,386
0
votes
1
answer
44
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.
...
- 54.2k
5
votes
2
answers
927
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 ...
- 11
38
votes
10
answers
9k
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.
- 3,042
0
votes
0
answers
44
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 ...
- 11.1k
2
votes
1
answer
174
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 ...
- 8,602
0
votes
1
answer
65
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 ...
- 5,544
4
votes
3
answers
1k
views
Fast and accurate eigenvalue computation for 3x3 posdef matrices
I am looking for a very fast and efficient algorithm for the computation of the eigenvalues of a $3\times 3$ symmetric positive definite matrix.
The algorithm will be part of a massive computational ...
- 1
2
votes
2
answers
3k
views
How Jacobian matrix helps optimization faster?
I tried some python optimization functions and some of them needed Jacobian matrix prior for faster convergence. I understand Jacobians are basically transformation matrices that data from one space ...
- 111
8
votes
0
answers
281
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,273
3
votes
1
answer
56
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 ...
- 11.1k
0
votes
0
answers
47
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....
- 933
1
vote
0
answers
31
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
132
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,273
3
votes
0
answers
117
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
11
votes
5
answers
5k
views
Memory efficient implementations of partial Singular Value Decompositions (SVD)
For model reduction, I want to compute the left singular vectors associated to the - say 20 - largest singular values of a matrix $A \in \mathbb R^{N,k}$, where $N\approx 10^6$ and $k\approx 10^3$. ...
- 111
1
vote
0
answers
75
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
83
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 ...
- 2,627
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
1
vote
1
answer
158
views
Lanczos memory complexity for dense matrices
Does the Lanczos algorithm remain memory efficient even if the original Hermitian matrix is dense?
CommunityBot
- 1
3
votes
1
answer
197
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
2
votes
1
answer
144
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
$$
...
- 11.1k
11
votes
1
answer
9k
views
cholesky factorization of block matrices
I have a block matrix (either 2x2 blocks or 3x3 blocks) which is the covariance matrix for a joint space of two or three multivariate normal variables. ie
...
- 103
7
votes
2
answers
392
views
Choice of iterative solver for a sparse asymmetric matrix with symmetric structure
I have a sparse $n\times n$ matrix $A$ with a pretty interesting structure. It has a block structure with a symmetric structure but asymmetric blocks. Expressed mathematically the block $A_{jk} = A_{...
- 544
1
vote
0
answers
64
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
1k
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 ...
- 2,054
-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 ...
- 283
5
votes
1
answer
459
views
Converting distance matrix back into original data
Suppose that we have $N$ points, and a distance matrix $D \in \mathbb{R}^{N \times N}$ describing the Euclidean distance among those points. For now, assume that we do not necessarily know how many ...
- 332
2
votes
0
answers
68
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
46
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,355