# 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
Filter by
Sorted by
Tagged with
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
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
112 views

1k views

### Calculate partial trace of an outer product in Python?

I have a python implementation of calculating the partial trace over select dimensions. ...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 "...
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 ...
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....
1 vote
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 ...
132 views

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 ...