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.
128
questions
5
votes
3answers
836 views
Seemingly non-unique Cholesky factor via QR rectangularisation
I am trying to implement an algorithm from a paper which makes use a QR factorization of a real matrix $A$ as a means of one of forming the Cholesky factor of $A^T A$ without explicitly forming $A^T A$...
5
votes
2answers
316 views
How “sparse” should a sparse matrix be to see benefits?
I have a matrix, whose size scales as $2^N$ (assume even $N$). In each row of the matrix, only about $2^{N/2}$ of the entries are filled ($N$ can be somewhere between 10 and 40, depending on what's ...
5
votes
3answers
6k views
Algorithm for Principal Eigenvector of a Real Symmetric 3x3 Matrix
I have a 3x3 covariance matrix (so, real, symmetric, dense, 3x3), I would like it's principal eigenvector, and speed is a concern. Is there a fast algorithm for this specific problem? I've seen ...
5
votes
2answers
3k views
Fast algorithms to find the eigenvalues of some matrix on intervals of interest
I am curious how to quickly compute the eigenvalues for arbitrary matrices, sparse or dense, restricted on some given interval of interest.
Suppose we have an arbitrary $n\times n$ matrix $A$, ...
4
votes
1answer
130 views
Constructing the origin position by transforming distance information
Suppose a set of $n$ points, $n\in M$, is given in some $d-$dimensional space, $X\in\mathbb{R}^{n\times d}$. Among these $n$ points, some $k\in K$ are selected, so $k<n$, and the distances from ...
4
votes
2answers
183 views
What mapping strategy should I use when solving many large linear systems of equations?
I am working on a problem that involves solving many (thousands) of distinct linear systems of equations, each with thousands of variables. Let's assume that the size of each matrix is exactly the ...
4
votes
2answers
120 views
Term for the typical “linear in the larger dimension, quadratic in the smaller” cost for linear algebra
Many dense linear algebra decompositions (QR, SVD...) on an $m\times n$ matrix have cost
$$
O(\max(m,n)\min(m,n)^2)
$$
when implemented in practice on a computer. Is there a colloquial name or a more ...
4
votes
2answers
203 views
How do the properties of a matrix affect the linear system solving
For a general matrix A, there are many properties to describe it: symmetric positive definite or indefinite, condition number, spectrum and so on. I am curious about how these properties affect the ...
4
votes
1answer
162 views
Factorization for reweighted least squares
I am solving a problem using an iteratively-reweighted least squares method: http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares
Essentially this requires solving a number of least-...
4
votes
1answer
54 views
Configuration shift for determination of a true dimensionality
What would then be the way to determine a true dimensionality of a configuration of points $X\in\mathbb{R}^{n\times k}$ based on its Gram matrix $G=XX^T$? The "true" dimensionality refers to the ...
4
votes
1answer
741 views
Thomas algorithm for 3D finite difference
For 1D finite difference, the resulting linear system is tri-diagonal and can be solved in O(n) using the Thomas algorithm.
I am trying to solve a finite ...
3
votes
1answer
159 views
Derivatives of Approximate Matrix inverses
I am cross posting this question to the mathermatics stack exchange. please find it either at this link, https://math.stackexchange.com/q/2952989/430980, or below:
I have a question concerning the ...
3
votes
0answers
107 views
Backward stable algorithm to get orthogonal projection onto the column space of a matrix
I have to find the orthogonal projection of a vector $b$ onto the matrix $A$ of size $m \times n$.
In my application, I don't have the luxury of calculating the QR factorization. All I have are ...
3
votes
2answers
167 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$.
...
3
votes
0answers
384 views
On solution of a class of discrete-time Lyapunov equation for systems with multiplicaitve noise
Let's consider the following equation
$$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$
where $p$ is an positive integer and $C$ is a known positive semidefinite matrix. If we augment $F=[F_{1}...F_{p}]$ ...
3
votes
2answers
3k views
C++ Library: What is the common libraries that do polynomial arithmetic?
I need to know what libraries (in C++) support polynomial arithmetic specially over a field. So I can give to it an array of coefficients of polynomial over a field and it returns the roots of ...
3
votes
1answer
139 views
Efficient Triangularisation of $\mathbf{S} = \operatorname{triag}\left(\mathbf{A}\right)$ ; $\mathbf{S}\mathbf{S}^T = \mathbf{A} \mathbf{A}^T$
The most computationally intensive part of my application is the triangularisation of a matrix, $\mathbf{S} = \operatorname{triag}\left(\mathbf{A}\right)$, such that $\mathbf{S}\mathbf{S}^T = \mathbf{...
3
votes
2answers
1k views
How Do I solve large systems given UMFPACK memory limitations?
I am trying to solve a system of equations (A x = b) for 3D heat diffusion (i.e. each equation has at most 7 terms not including the constant "b" term) using UMFPACK with boost numeric bindings to C++....
3
votes
1answer
908 views
Is a checkerboard block decomposition of a matrix useful when solving a linear system with a parallel conjugate gradient method?
According to these lecture notes, a checkerboard block decomposition should exhibit better scalability when applied to parallel matrix-vector multiplication (presumably because of greater cache hit ...
2
votes
0answers
97 views
C++: How to find the roots of polynomial modulus N [duplicate]
I need to know what library, given a vector of coefficients and modulus N return the roots of polynomial modulus N. The library should support big integer. I'm coding in C++.
2
votes
1answer
82 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} } \...
2
votes
0answers
68 views
How can I numerically solve a saddle point problem with repeated constraints?
I am interested in numerically solving the following constrained minimization problem; Find the value of $x\in \mathbb{R}^n$ that minimizes $f$ where
$f\colon \mathbb{R}^n\to \mathbb{R}$ is defined ...
1
vote
1answer
84 views
Invert a matrix only on a subset of variables / Compute the “equivalent circuit”
Suppose I have a complicatedly shaped conductor with inhomogeneous conductivity. The conductor is modeled using the Finite Element Method. The conductor has electrical contacts on both ends. Those ...
1
vote
3answers
348 views
rank-deficient NNLS
I want to find the minimum-norm solution to a rank-deficient least-squares problem, subject to positivity constraints, e.g.
$$\min_x\ \|x\|^2 \quad s.t.\quad Ax = b,\ x \geq 0$$
where $A$ is large, ...
1
vote
1answer
133 views
TDMA with 3rd order upwind scheme
I'm trying to implement a model I found in a paper, but there is something I do not understand. The authors say they use TDMA to solve their equations; however, they use a 3rd order upwind biased ...
0
votes
1answer
168 views
How to compute matrix representation of $\hat{y}\frac{\partial}{\partial x}$?
I have a 2-dimensional system which I would like to solve numerically (I'm using finite difference method right now), and its an eigenvalue problem. I have a term that looks like $H\psi(x,y) = [-\frac{...
0
votes
1answer
223 views
Is there any rapid way to calculate the determinant of NXN covariance matrix?
I searched the web and found some C code for calculating the determinant of a $n\times n$ matrix. This code however seems timing complexity, and run pretty slow especially when handling a larger ...
-1
votes
2answers
220 views
$LU$ factorization
Our task is to implement a factorization routine that given A in a suitably efficient data structure returns the factors $L$ and $U$ where $L$ is unit lower triangular and $U$ is upper triangular. In ...
