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.

Filter by
Sorted by
Tagged with
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 ...

1 2
3