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.

0
votes
0answers
17 views

Gaussian Elimination Using Fortran

I developed the code below for performing gaussian elimination in order to evaluate the determinant of a matrix: ...
2
votes
2answers
183 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 ...
0
votes
1answer
38 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}\\...
0
votes
0answers
80 views

Gaussian Elimination with Fortran 90 [closed]

I am having some issues in implementing this sample code.Calculating the determinant of a matrix: ...
9
votes
3answers
298 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
0answers
90 views

How to solve extremely large scale linear system

I have a extremely large scale liner system equation. It stems from the minimization of $$ E(\{\widetilde{C_{i}}\}) = \sum_{i}\left[ \left( 1-\psi _{i}\right) \left\| \widetilde{C_{i}}-\sum_{j\in{N_{i}...
5
votes
1answer
142 views

How can I apply Euler's Method to predict a point in time rotating around multiple axis'

I am xposting this from my original stackoverflow question where I was presented with a coding challenge that I have been able to narrow down extensively and I think it lies with Euler's Method. Here'...
3
votes
2answers
49 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 ...
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. ...
2
votes
1answer
100 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\...
6
votes
1answer
105 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 ...
3
votes
1answer
126 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 ...
2
votes
2answers
94 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?
6
votes
1answer
208 views

Eigenvector with maximum overlap

Given a matrix $M$ and a vector $v$, is there an efficient method to find the normalized eigenvector of $M$ that is closest to $v$, in that it has maximal overlap. More explicitly, a vector $v$ can be ...
6
votes
1answer
72 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 \...
1
vote
2answers
120 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 ...
9
votes
3answers
157 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 ...
4
votes
2answers
98 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 ...
2
votes
1answer
176 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$...
5
votes
1answer
96 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 ...
4
votes
1answer
86 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. (...
1
vote
1answer
88 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 ...
3
votes
0answers
60 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 ...
5
votes
1answer
139 views

Matlab help related with the scaled Newton's iteration method

I need a little help with Matlab code for the method mentioned in this paper for computing the inverse of the matrix. In this paper, the author presented scaled Newton iteration given by $X_{k+1} = \...
155
votes
10answers
117k views

Recommendations for a usable, fast C++ matrix library?

Does anyone have recommendations on a usable, fast C++ matrix library? What I mean by usable is the following: Matrix objects have an intuitive interface (ex.: I can use rows and columns while ...
2
votes
0answers
88 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 ...
4
votes
1answer
374 views

LU Decomposition of PSD Matrix + Diagonal Matrix

If I have a psd, symmetric matrix $\mathbf{A}$ and I need to do LU decomps on $\mathbf{B_i}= \mathbf{A} + \mathbf{D_i}$ (where $\mathbf{D_i}$ is a diagonal psd matrix, where $\mathbf{D_i}$ changes ...
8
votes
0answers
178 views

Imbalance of variables in Mixing Newton's method and Linear solver for a Non-linear system

Problem Solving a non-linear system of equations. The number of variables is the same as the number of equations. When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{...
2
votes
1answer
80 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
103 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$...
1
vote
1answer
87 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. ...
6
votes
3answers
218 views

Nonlinear eigenvalue problem - MATLAB code

I'm trying to solve a nonlinear eigenvalue problem in MATLAB, still without success. It's a problem about graphene plasmonics. The nonlinear eigenvalue problem is given below: \begin{equation} \frac{...
6
votes
1answer
529 views

Estimate extreme eigenvalues with CG

CG may be used to estimate the extremal eigenvalues of a SPD matrix (by computing eigenvalues of tridiagonal matrix associated with the Lanczos algorithm). After a few iterations the largest ...
3
votes
1answer
97 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 ...
3
votes
1answer
73 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 ...
4
votes
0answers
61 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 ...
2
votes
0answers
81 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
121 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
79 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 ...
4
votes
2answers
150 views

Modifying solution of system of linear equations

Suppose that we have a linear system of equations $$Ax=b$$ where $A$ is a $3 \times 3$ matrix and $x$ and $b$ are $3$-vectors. Let $y$ denote the solution of this system of equations. I want to ...
3
votes
0answers
65 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 ...
3
votes
2answers
118 views

Factoring the sum of two matrices

Given \begin{equation} A_i=B+C_i \end{equation} where $A_i$,$B$ and $C_i$, $i=1,\dotsc,N$ are large square matrices, $B$ is symmetric, $C_i$ are zero matrices aside for a square block on the diagonal. ...
-1
votes
1answer
67 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 ...
0
votes
1answer
42 views

Slightly change two vectors to satisfy a constraint

$\vec{a}\cdot\vec{b} \approx c$ $\vec{\alpha} \cdot \vec{\beta} = c$ $\vec{\alpha}$ is close to $\vec{a}$ and $\vec{\beta}$ is close to $\vec{b}$ Given $\vec{a}$, $\vec{b}$ and c, how to find $\vec{\...
8
votes
2answers
194 views

How does the QR algorithm applied to a real matrix returns complex eigenvalues?

I'm a noob into eigenvalues algorithms, but something call my attention. QR algorithm works with real/complex matrices producing real/complex eigenvalues. However, it can not produce complex ...
1
vote
1answer
82 views

Why does Newton's method with Linear Equality Constraints use KKT condition?

Goal: Optimize convex function $f(\vec{x})$ subjected to constraint $A\vec{x} = \vec{b}$ starting at a point $\vec{x}_0$ that satisfies the constraint. The problem only has equality constraint. Why ...
2
votes
0answers
24 views

Randomized Submatrix of a Sparse Matrix

I have a sparse square matrix $A$ with size $n \times n$ and number of nonzero entries $nnz$. The goal is making a sub-matrix $B$ with $s$ nonzeros which are randomly chosen from $A$. Duplicates are ...
5
votes
2answers
126 views

Fast and Numerically Stable Pairwise Distance Algorithms

I'm looking for resources on fast, numerically stable pairwise euclidean distance algorithms. In particular, suppose $A \in \mathbb{R}^{M \times D}$ and $B \in \mathbb{R}^{N \times D}$ are two sets of ...
1
vote
1answer
71 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 ...
2
votes
1answer
83 views

Inverting small matrices: canned factorization versus explicit formula

I am interested in solving a large number of small linear systems of equations, $Ax=b$, with $A$ either $2\times2$ or $3\times3$. Assuming none of these systems are actually singular, is there ...