Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
71 views

In iterative methods, are matrix decompositions considered useful for implementation?

When we study an iterative method from textbooks, for example, see the Gauss-Seidel Method, the given matrix is decomposed with suitable splittings. In the example, $A = L+U$. So we can proceed with ...
5
votes
2answers
311 views

Python: vectorizing a structured linear system solve

Overview I am looking for a way to solve a structured linear system in Python without using a for loop (preferably using vectorization, if possible). Background Consider the following linear system:...
2
votes
1answer
60 views

Re-using LU factorization within iterative (?) setup for a sum of two matrices

So, I would love to make at least some use of my preexisting data, no matter how small, and just out of ideas. Maybe I am just a prisoner of a Kahneman-like theatre-ticket paradox, and don't know ...
4
votes
1answer
146 views

Accurate way of getting the square root inverse of a positive definite symmetric matrix

What is the most accurate algorithm to get the square root inverse of a positive definite symmetric matrix? I am not looking as much for efficiency, though using quadruple precision computation is out ...
2
votes
2answers
163 views

Compiled c++ code runs much faster with double than float. Explanation?

I am still rather new on here and I hope question is suitable for this forum otherwise please help me migrate it to greener pastures. I am an electrical engineer specializing in applying mathematics ...
5
votes
0answers
45 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 ...
4
votes
2answers
68 views

How to efficiently invert $K \otimes M+I_T\otimes \Sigma$?

I'm looking for a way to efficiently invert $$K \otimes M+I_T\otimes \Sigma$$ where the inverses for $M,K$ exist. $I_T$ is the identity matrix of dimension $T$, and $\Sigma$ is a diagonal matrix, with ...
2
votes
1answer
35 views

Discretization with non-constant matrix containg entries form unknown vector

Consider a system of PDEs $$ \begin{cases} u_t = \nabla \cdot (D(u)\nabla u) + \frac{c}{K_U+c}u-ku\\ c_t = d_c\Delta c -\frac{\nu_U c}{K_U + c}u \end{cases} $$ with some boundary conditions. Here, $D(...
29
votes
15answers
8k views

Good examples of “two is easy, three is hard” in computational sciences

I recently encountered a formulation of the meta-phenomenon: "two is easy, three is hard" (phrased this way by Federico Poloni), which can be described, as follows: When a certain problem is ...
1
vote
0answers
34 views

Stability of SVD, Eigendecompositions, and pseudoinverse procedures in modern LAPACK routines

I have proposed an optimisation algorithm which I claim has improved upon the previous algorithm in a number of ways. One of these claims is that my proposed solution requires no explicit SVD and ...
2
votes
1answer
67 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
1answer
55 views

Rank of Hadamard Product with Masked Matrix

I have a matrix $A\in\{0,1\}^{d\times n}$ and $rank(A)=d,d<n$, and another matrix $X\in \mathbb{R}^{d\times n}$, but I do not know the rank of $X$. What can we say about the rank of their Hadamard ...
2
votes
1answer
75 views

How to compute the determinant of Hessian of a multivariable function?

I have a function $F(\vec x)$ of many variables (let's say in the order of hundreds of thousands). I need to compute the determinant of the Hessian matrix at the point $x_0$. Is there a way to ...
0
votes
0answers
52 views

Bound for Expectation of Singular Value

In my case, $X_{\boldsymbol{\delta}}\in\mathbb{R}^{d\times M}$ is a function of Rademacher variables $\boldsymbol{\delta}\in\{1,-1\}^M$ with $\delta_i$ independent uniform random variables taking ...
3
votes
2answers
62 views

Convexity of Sum of $k$-smallest Eigenvalue

If I have a real positive definite matrix $A\in\mathbb{R}^{n\times n}$, and denote its eigenvalues as $\lambda_1\leq \lambda_2 \leq ... \leq \lambda_n $. Define the function as $f(A)=\sum_{i=1}^{k} \...
0
votes
1answer
42 views

An Upper Bound of $\left<H,X\right>_F$ with Constrainted Rank

We have $X=[\mathbf{x}_1,\mathbf{x}_2...,\mathbf{x}_n]\in\mathbb{R}^{d\times n}$, $H=[\mathbf{h}_1,\mathbf{h}_2...,\mathbf{h}_n] \in\mathbb{R}^{d\times n}$, and $d<n$. $H$ has rank $r\leq d$ and $X$...
2
votes
1answer
81 views

Which pseudo-inverse to compute when Inverse is not possible? (No linear solve)

Let us assume that we have a function, $f(A)=\text{vec}(A^{-1})^\intercal B$, dependent on $A^{-1}$. However, due to some machine-precision limitations, the programming language I'm using cannot ...
5
votes
2answers
169 views

Computing any element of the null space of a singular matrix

Given a singular matrix $A$, what is the fastest method to find a single non-zero solution to $Ax=0$? Note that we are not looking for the whole kernel, we just want any non-zero vector in it. I ...
2
votes
1answer
106 views

A fast way to check if a Matrix is ill-conditioned, and turning it into well-conditioned

I'm running a simulation, and some linear solvers are returning a message of ill-conditioned matrix. Hence, I'm looking for a fast, easy to implement, method to detect if a matrix is ill-conditioned, ...
2
votes
1answer
21 views

Determine image of hypercube under linear map

Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
1
vote
0answers
92 views

Connection between piecewise linear basis functions and RELU activation function

ReLU activation is defined as follows $$\sigma(x)=\max(0, x).$$ Let's assume that I have deep network of 1 hidden layer, than output from my layer has form $$ f(x)= \sigma(Wx +b), $$ where matrix W ...
1
vote
1answer
63 views

Gaussian Elimination Using Fortran [closed]

I developed the code below for performing gaussian elimination in order to evaluate the determinant of a matrix: ...
1
vote
1answer
53 views

Product of rank one updates as a low rank update for quasi newton/BFGS

I'm trying to improve the speed of the following iteration to calculate $s_k$: $$B_k^{-1} = \Bigg( I + \frac{s_{k}s_{k-1}^T}{||s_{k-1}||^2}\Bigg)...\Bigg(I+ \frac{s_1s_0^T}{||s_0||^2}\Bigg) B_0^{-1}\\...
9
votes
3answers
320 views

fastest linear system solve for small square matrices (10x10)

I am very interested in optimizing the hell out of linear system solving for small matrices (10x10), sometimes called tiny matrices. Is there a ready solution for this? The matrix can be assumed ...
0
votes
1answer
56 views

Finding Matrix inverse with LU and repeted left division calls

Hello I am in a basic numerical methods class and our teacher has given us an algorithm which can compute the inverse of a matrix other than using MATLAB's built in library function. ...
3
votes
2answers
57 views

Finding exact rational solution to linear integer equations in Matlab

I have a linear system of equations $$Ax=b$$ where $A$ is an $N\times N$ matrix with integer values, and $b$ is a $N\times 1$ vector with integer values. Due to prior knowledge, I know that I am ...
6
votes
1answer
108 views

numerical solution of an under-determined linear equation in high dimensions

I need to solve a linear regression problem $$Ax=y$$ which is hugely underdetermined. I have around $10^6$ features but only $10^3$ equations. So $A$ is a $1,000\times 1,000,000$ matrix and $y$ a ...
2
votes
1answer
104 views

Projection onto the set of Orthogonal matrices

Let $M \in \mathbb{R}^{n \times n}$ and denote the set of Orthogonal matrices by \begin{equation} \mathcal{O}_{n} = \left\lbrace Q \in \mathbb{R}^{n \times n} \colon QQ^{T} = \mathbb{I}_{n} \right\...
2
votes
2answers
113 views

Asymptotic Complexity of Gaussian Elimination using Complete Pivoting

I would like to know the algorithm asymptotic complexity with Complete Pivoting. With partial pivoting, it is known to be $O(n^3)$. Is it the same for complete pivoting?
1
vote
2answers
141 views

Condition number of a matrix

I saw some definition that if $$M=\max_{x\not=0} \tfrac{\|Ax\|}{\|x\|} \quad\text{and}\quad m=\min_{x\not=0} \tfrac{\|Ax\|}{\|x\|} \,,$$ the condition number of $A=M/m$. In my opinion, If we have a ...
6
votes
1answer
76 views

Solving a Hadamard + Linear System

I need to solve a matrix equation which contains a Hadamard product and a standard matrix multiplication: $$A\odot X + BX = C$$ where $A, C, X \in \mathbb{R}^{m \times n}$, $B \in \mathbb{R}^{m \...
9
votes
3answers
191 views

What is the reason that LAPACK uses $\tau$ in QR decomposition (instead of normalizing the reflection vector)?

LAPACK's QR routine stores Q as Householder reflectors. It scales the reflection vector $v$ with $1/v_1$, so the first element of the result becomes $1$, so it doesn't have to be stored. And it stores ...
3
votes
1answer
447 views

Which C++ linear algebra library is probably the fastest on solving huge sparse [square matrix] linear system?

I am developing a 2D CFD solver for fluid-particle interaction. To solve Navier-Stokes equations on a grid of size $10000\times 10000$ cells (or >1 million cells), a large linear system $Ax=b$ with $A$...
4
votes
1answer
91 views

Numerically find the nearest positive semi definite matrix to a symmetric matrix

I have a symmetric matrix $M$ which I want to numerically project onto the positive semi definite cone. To do so, I decompose it into $M = QDQ^T$ and transform all negative eigenvalues to zero. (...
5
votes
1answer
101 views

Nullspace calculation of large matrix with rational numbers without round-off errors (exact)

I need to calculate a basis of the nullspace of large (up to a thousand columns and rows) matrices. For my application, it is very important that no round-off errors occur during the computation, so I ...
1
vote
1answer
96 views

Computing the Inverse of a matrix, using the Cholesky decomposition

I have to compute $CA^{-1}B$ and $CA^{-1}x$, where $A,B,C$ are conformable matrices and $x$ is a vector. I've read that the a very computationally stable way to compute these inverses is by computing ...
4
votes
0answers
66 views

Block matrix and DSYRK

I want to compute the matrix $$ A = \sum_{i=1}^N v_i v_i^T $$ where each $v_i$ is a given vector of length $2500$, so that $A$ is $2500 \times 2500$, and my $N$ is about 2 million. Rather than call ...
4
votes
3answers
252 views

Best software to do big number calculations quickly

I am trying to do some work on some math conjecture. I am testing the conjecture numbers using very large math numbers (100+ digits ). I am currently using python to test these numbers. In the ...
2
votes
0answers
203 views

Discrete-time Algebraic Riccati Equation (DARE) solver in C++

I need to use a Discrete-time Algebraic Riccati Equation (DARE) solver for an embedded controller (with limited processing power) in a research project and sadly, I can't find any implementation of it ...
2
votes
1answer
81 views

Checking positive definiteness on a hyperplane

Is there a faster way to check whether $A\in\mathbb{R}^{n\times n}$ is positive definite on $b^{\bot}:=\{x\in \mathbb{R}^{n}: x\cdot b=0\}$ than ...
1
vote
1answer
120 views

Operation count for GMRES

One can use GMRES as it is, but there is also a version of GMRES called k-step restarted GMRES, which is used for large matrices, where $k$ is some fixed number of steps after which we take a new $x_0$...
3
votes
1answer
125 views

How to find the nearest/a near positive definite from a given matrix?

I'm given a matrix. How do I find the nearest (or a near) positive definite from it? The matrix can have complex eigenvalues, not be symmetric, etc. However, all its entries are real valued. The ...
4
votes
0answers
66 views

Improving convergence of Jacobi iteration to Schur form

I'm using SIMD processor arrays to compute the eigen-decomposition for large numbers of small (up to $32\times 32$) matrices. For assorted technical reasons, Jacobi iteration maps well to the SIMD ...
3
votes
1answer
85 views

Condition number of matrix and effects of round off errors

In my numerical linear algebra class, I learned that for some matrices, it could have an element that is a very small number that is approximately 0 (and many orders of magnitude different from all ...
2
votes
1answer
108 views

A Bound for the inverse of the sum of identity and triangular matrix

I wonder if there are any theorems which can help me to calculate an upper bound for the spectral norm of: $$\left\| \left[ I + \sum_{i=1}^{\overline{n}\in\mathbb{N}} \big( C_i - I\big)\right]^{-1}\...
4
votes
1answer
125 views

Fast matrix multiplication with matrix elements computed on-the-fly (without forming the matrix)

Is there any library or routine for high-performance matrix-matrix product, where the matrix elements are computed on-the-fly using a given function of $i$ and $j$? More specifically, in the problem ...
3
votes
0answers
80 views

Why the MIRACLE of Lanczos/CG-like?

Lanczos/Arnoldi/Rietz/CG-like algorithm share the same core strategy... In each, a little miracle appears, most of the Gram-Schmidt inner products are zeroes! In others words, new direction need only ...
1
vote
1answer
97 views

Multigrid preconditioner for conjugate gradient methods

When solving $A*x=b$ using preconditioned conjugate gradient methods one has to solve $z=K^{-1}*r$ for the preconditioning where $K$ is the preconditioner of $A$ and $r$ is the residual vector. ...
3
votes
0answers
68 views

Element Preconditioner

Im just working on a preconditioner for the linear equation system $Ax = b$ arising in FEM for elliptic PDE. $A$ is a s.p.d Matrix with real valued entries. I read something about the element by ...
-1
votes
1answer
70 views

Relation of Condition of a Matrix and Convergency

Can anybody explain me the relation between the condition of a Matrix and the convergency of a problem. For example how is the relation between the condition of the stiffness Matrix occuring in FEM ...