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 [numerical-linear-algebra]

Questions on the various algorithms used in linear algebra computations (matrix computations).

32
votes
2answers
58k views

Distance/Similarity between two matrices

I'm in the process of writing an application which identifies the closest matrix from a set of square matrices $M$ to a given square matrix $A$. The closest can be defined as the most similar. I ...
23
votes
1answer
22k views

block matrix multiplication

If $A,B$ are $2 \times 2$ matrices of real or complex numbers, then $$AB = \left[ \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right]\cdot \left[ \begin{array}{cc} b_{11} ...
21
votes
4answers
16k views

Fast algorithm for solving system of linear equations

I have a system of $N$ linear equations, $Ax=b$, in $N$ unknowns (where $N$ is large). If I am interested in the solution for only one of the unknowns, what are the best approaches? For example, ...
18
votes
4answers
12k views

Determining whether a symmetric matrix is positive-definite (algorithm)

I'm trying to create a program, that will decompose a matrix using the Cholesky decomposition. The decomposition itself isn't a difficult algorithm, but a matrix, to be eligible for Cholesky ...
16
votes
2answers
1k views

The benefit of LU decomposition over explicitly computing the inverse

I'm going to teach a linear algebra course in the fall, and I want to motivate the topic of matrix factorizations such as the LU decomposition. A natural question one can ask is, why care about this ...
16
votes
3answers
1k views

Fast computation/estimation of the nuclear norm of a matrix

The nuclear norm of a matrix is defined as the sum of its singular values, as given by the singular value decomposition (SVD) of the matrix itself. It is of central importance in Signal Processing and ...
13
votes
1answer
5k views

Using the Arnoldi Iteration to find the k largest eigenvalues of a matrix

I'm trying to obtain a general understanding of this algorithm which determines the k-largest eigenvalues of a matrix $A\in \mathbb{R}^{n\times n}$. How I see it: power iteration: take random ...
13
votes
2answers
201 views

How to get the SVD of $2AA^T-\operatorname{diag}(AA^T)$ given $A$ and its SVD $A=USV^T$?

Given a matrix $A\in R^{n\times d}$ with $n>d$, and we can have some fast ways to (approximately) calculate the SVD (Singular Value Decomposition) of $A$, saying $A=USV^T$ and $V\in R^{d\times d}$. ...
12
votes
4answers
17k views

How to compute the smallest eigenvalue using the power iteration algorithm?

I need to write a program which computes the largest and the smallest (in terms of absolute value) eigenvalues using both power iteration and inverse iteration. I can find them using the inverse ...
12
votes
2answers
5k views

LU Decomposition vs. Cholesky Decomposition

What is the difference between LU Decomposition and Cholesky Decomposition about using these methods to solving linear equation systems? Could you explain the difference with a simple example? Also ...
12
votes
1answer
636 views

Computing the SVD factorization on C++ (using the proof of the existence of the SVD factorization)

I am doing a C++ program that computes the SVD factorization of a real matrix A without using any known library of algebra that contains the implementation. In addition, QR descomposition is not ...
11
votes
6answers
8k views

Determinant of large matrices: there's GOTTA be a faster way

WARNING this is a very long report and is likely going to cause boredom. be warned!! I've heard of the determinant of small matrices, such as: $$\det \begin{pmatrix} a&b\\ c&d\\ \end{...
11
votes
3answers
6k views

What is the practical impact of a matrix's condition number?

Let's say I am trying to solve a square linear system $Ax = b$ for whatever reason. A perturbation $\delta b$ in $b$ will lead to a perturbation $\delta x$ in $x$, whose relative norm is bounded by ...
11
votes
2answers
223 views

Determinant of $5 \times 5$ Boolean matrix

Consider the set of $5 \times 5$ matrices with $10$ entries equal to $1$ and the other $15$ entries equal to $0$. I would like to know how many such matrices have nonzero determinant. Is there a way ...
10
votes
6answers
947 views

$\left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right)$ not diagonalizable

I would like to ask you about this problem, that I encountered: Show that there exists no matrix T such that $$T^{-1}\cdot \left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right)\...
10
votes
2answers
5k views

Trace minimization with constraints

For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under 'either' one of these constraints: a) Sum of squares of Euclidean-distances between pairs ...
10
votes
2answers
3k views

Algorithm to find an orthogonal basis (orthogonal to a given vector)

Let $K$ be a given integer, with $K$ even (and "large"). Let $\mathbf{v} \in \mathbb{R}^{K \times 1}$ be a given non-zero (column) vector. Write a (possibly efficient) algorithm to construct a matrix $...
10
votes
3answers
20k views

Proof that Newton Raphson method has quadratic convergence

I've googled this and I've seen different types of proofs but they all use notations that I don't understand. But first of all, I need to understand what quadratic convergence means, I read that it ...
10
votes
2answers
489 views

Advice in Bachelor Degree

First of all, I´m very sorry for my bad english, especially writing. Ok, for differents problems i´m studing a Bachelor degree in Mathematics. These degree is online. Now, the problem with my school ...
10
votes
1answer
3k views

Augmented Reality Transformation Matrix Optimization

i am a software developer, i'm working on an Augmented Reality system. I'd like to receive some advice in order to optimize my math model. My program has to be slim and fast. Here's the situation: ...
10
votes
0answers
221 views

How to solve linear system of form $(A \otimes B + C^{T}C)x = b$ when $A \otimes B$ is too large to compute?

For the given linear system: $$(A \otimes B + C^{T}C)x = b$$ where $\otimes$ is the Kronecker product, $A$ and $B$ are dense and symmetric positive-definite, and $C^{T}C$ is a sparse symmetric block ...
9
votes
3answers
1k views

I get a wrong determinant - why?

I'm trying to calculate the following determinant: $$\begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_n \\ a_0 & x & a_2 & \dots & a_n \\ a_0 & a_1 & x & \dots &...
9
votes
5answers
3k views

Finding nonnegative solutions to an underdetermined linear system

Here's the environment of my problem: I have a linear system of 4 equations in 8 unknowns (i.e. $Ax = b$, where $A$ is $4 \times 8$, $x$ is $8 \times 1$, and $b$ is $4 \times 1$, with $A$ given and $b$...
9
votes
1answer
5k views

Block inverse of symmetric matrices

Let us assume we have a symmetric $n \times n$ matrix $A$. We know the inverse of $A$. Let us say that we now add one column and one row to $A$, in a way that the resulting matrix ($B$) is an $(n+1) \...
9
votes
1answer
2k views

Uniform sampling of points on a simplex

I have this problem: I'm trying to sample the relation $$ \sum_{i=1}^N x_i = 1 $$ in the domain where $x_i>0\ \forall i$. Right now I'm just extracting $N$ random numbers $u_i$ from a uniform ...
9
votes
3answers
10k views

Time complexity of LU decomposition

I am trying to derive the LU decomposition time complexity for an $n \times n$ matrix. Eliminating the first column will require $n$ additions and $n$ multiplications for $n-1$ rows. Therefore, the ...
9
votes
3answers
3k views

Are there any decompositions of a symmetric matrix that allow for the inversion of any submatrix?

I am given a $J \times J$ symmetric matrix $\Sigma$. For a subset of $\{1, ..., J\}$, $v$, let $\Sigma_{v}$ denote the associated square submatrix. I am in need of an efficient scheme for inverting $\...
9
votes
1answer
2k views

Numerically stable method for angle between 3D vectors

I'm looking for a numerically stable method for computing the angle between two 3D vectors. Which of the following methods ought to be preferred? Method 1: $$ u\times v = ||u||~||v|| \sin(\theta) \...
9
votes
1answer
1k views

Fast algorithm for approximating Eigenvalue distribution of large sparse matrix

I am interested in the eigenvalue distribution of a huge $2^{16}$x$2^{16}$ Hermitian sparse matrix with spectrum contained in $[-1,1]$. That is I don't need to know all eigenvalues exactly, but rather ...
9
votes
1answer
899 views

Sum of idempotent matrices is Identity

[Ciarlet, Problem $1.1-10$] Let $A_k$, $1 \leq k\leq m$, be matrices of order $n$ satisfaying $$\sum_{k=1}^mA_k\ =\ I.$$ Show that the following conditions are equivalent. $A_k = (A_k)^2$, ...
8
votes
2answers
8k views

matrix similarity upper triangular matrix

How to show: Any matrix A with real or complex entries is similar to an upper triangular matrix M whose diagonal entries are the eigenvalue of A. Thank you!
8
votes
5answers
3k views

Is there a faster way to calculate a few diagonal elements of the inverse of a huge symmetric positive definite matrix?

I asked this on SO first, but decided to move the math part of my question here. Consider a $p \times p$ symmetric and positive definite matrix $\bf A$ (p=70000, i.e. $\bf A$ is roughly 40 GB using 8-...
8
votes
3answers
975 views

Matlab code to compute the smallest nonzero singular value of the matrix without using SVD

I want to compute the smallest nonzero singular value of the matrix A, which is defined as follows. Let $B = rand(500, 250)$, $A = B*B^t$, where $t$ denotes the transpose of the matrix. I found ...
8
votes
2answers
2k views

Inverse of the sum of a symmetric and diagonal matrices

I have two matrices $A$ and $B$ with quite a few notable properties. They are both square. They are both symmetric. They are the same size. $A$ has $1$'s along the diagonal and real numbers in $(0 ...
8
votes
3answers
2k views

What are the real life applications of quadratic forms?

What are the real life applications of quadratic forms? I have used them to sketch conics but are there any other applications?
8
votes
1answer
2k views

What would be a good method for finding the submatrix with the largest sum?

This question is from an ongoing contest which ends in 4 days. It is this problem from the October Challenge. Given:A Matrix (Not necessarily square) filled with negative and positive integers.What ...
8
votes
1answer
169 views

Vandermonde matrices nullspaces and notation

I'm following the book Mimetic Discretization Methods by Castillo and Miranda, reading the page 209-211, it states the following: Let $V(m;G)$ be a Vandermonde matrix, of order $m$ with generator $G =...
7
votes
1answer
242 views

Generate arbitrary numerically invertable matrix

I'm designing a unit-test for a matrix inversion function. Currently I make a random matrix as a test case by generating its elements with random numbers uniformly distributed in $[0,1)$. If I ...
7
votes
2answers
296 views

What new insights does numerical analysis give on linear algebra?

I know linear algebra decently well, but I've never taken a numerical analysis course. However, I've heard that it provides a good intuition for the subject. Assuming that I'm already familiar with ...
7
votes
1answer
5k views

What is the time complexity of conjugate gradient method?

I have been trying to figure out the time complexity of the conjugate gradient method. I have to solve a system of linear equations given by $$Ax=b$$ where $A$ is a sparse, symmetric, positive ...
7
votes
1answer
275 views

Why would $(A^{\text T}A+\lambda I)^{-1}A^{\text T}$ be close to $A^{\dagger}$ when $A$ is with rank deficiency?

In many applications that is not with high requirements, it is common to use $(A^{\text T}A+\lambda I)^{-1}A^{\text T}$ or $A^{\text T}(AA^{\text T}+\lambda I)^{-1}$ ($\lambda$ is small) to ...
7
votes
1answer
802 views

Precision and performance of Euclidean distance

The usual formula for euclidean distance that everybody uses is $$d(x,y):=\sqrt{\sum (x_i - y_i)^2}$$ Now as far as I know, the sum-of-squares usually come with some problems wrt. numerical ...
7
votes
1answer
2k views

Properties shared by similar and unitary similar matrices.

We know that matrices $A$ and $B$ are similar if there exists an invertible matrix $P$ such that $A=PBP^{-1}$ and they are unitarily similar if $P$ is unitary ($PP^*=P^*P=I$). I want to know : What ...
7
votes
1answer
654 views

Is Householder orthogonalization/QR practicable for non-Euclidean inner products?

The question Is there a variant of the Householder QR algorithm to orthonormalize a set of vectors with respect to an inner product if no orthonormal basis is known a priori? Background Let's ...
7
votes
1answer
168 views

Compute a diagonalizable matrix close in matrix exponential

It is known that for any matrix $A$, one can perturb $A$ slightly so that the resulting $A(\epsilon)$ is diagonalizable. I am wondering whether for any matrix $A$, $\epsilon>0$, there is an ...
7
votes
1answer
175 views

Singularity of a positive linear combination of rank one matrices

Given a set of rank one matrices $A_1,..,A_n$, we need to find out if there exists $x \in \mathbb R^n$ with $x\gg 0$ (i.e, positive) such that $$ \sum_{i=1}^n x_i A_i = x_1 A_1 + .... + x_n A_n $$ ...
7
votes
1answer
917 views

Floating point arithmetic operations when row reducing matrices

A numerical note in my linear algebra text states the following: "In general, the forward phase of row reduction takes much longer than the backward phase. An algorithm for solving a system is usually ...
7
votes
1answer
2k views

What is the Moore-Penrose pseudoinverse for scaled linear regression?

The matrix equation for linear regression is: $$ \vec{y} = X\vec{\beta}+\vec{\epsilon} $$ The Least Square Error solution of this forms the normal equations: $$ ({\bf{X}}^T \bf{X}) \vec{\beta}= {\bf{...
7
votes
1answer
404 views

Is this a block Toeplitz matrix?

What is the name of the following matrix? $$\begin{pmatrix} a & b & 0 \\ c & d & 0 \\ 0 & a & b\\ 0& c& d& \\ b & 0 & a \\ d & 0 & c\end{...
7
votes
0answers
200 views

Conditioning of the linear systems in the inverse or Rayleigh quotient iteration algorithms

I'm working through the book Numerical Linear Algebra by Trefethen and Bau. In Lecture 27 (and exercise 27.5), the following claim is made about the inverse iteration algorithm: Let $ A $ be a real, ...