Questions tagged [numerical-linear-algebra]

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

10
votes
0answers
222 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 ...
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, ...
7
votes
0answers
626 views

Simulating from a Multivariate Gaussian without Cholesky

I'd like to draw a sample from a multivariate Gaussian distribution $\mathcal{N}(\mu, \Sigma)$, where $\mu$ is the mean vector (can assume it to be $\boldsymbol{0}$), and $\Sigma$ is a sparse positive ...
6
votes
0answers
78 views

Numerically robust 2x2 determinant?

How can the determinant of a 2x2 matrix $$ \begin{vmatrix} a & b \\ c & d \end{vmatrix} = a d - b c $$ be computed in floating point without suffering unnecessary catastrophic cancellation? ...
6
votes
0answers
72 views

Maximizing the pairwise Frobenuis distance between M othrogonal matrices

I want to maximize the pairwise Frobenius distance between $M$ orthogonal matrices. That is, I'm looking for $Q_{i}, i = 1, 2, ... M$ such that \begin{equation*} \begin{aligned} & \underset{ 1 \...
6
votes
0answers
130 views

IEEE 754 as a mathematical space

Integer operations in computers (i.e. 32-bit integers) probably can be represented best by modular arithmetic (because of integer overflows/underflows). What about IEEE 754 floating point arithmetic? ...
6
votes
0answers
115 views

Is there a way to exploit the fact that the covariance matrix has a blocked structure to more easily compute the multivariate normal density?

I'm trying to minimize the (negative) multivariate normal log likelihood (dropping constants): $$ \log |\boldsymbol\Sigma|\,+(\mathbf{x}-\boldsymbol\mu)^{\rm T}\boldsymbol\Sigma^{-1}(\mathbf{x}-\...
5
votes
0answers
639 views

Numerical stability of Winograd short convolution algorithm

Similar to how Strassen matrix multiplication is an asymptotically faster matrix-multiplication algorithm, there exists a similar idea for convolution by (short) filters called Winograd convolution [1,...
5
votes
0answers
123 views

Invertibility of infinite order matrix

how the matrix $[e^{-(x_j-x_k)^2}]$ is invertible where $\{x_j\}$ be any real sequence such that $(x_{j+1}-x_j) >0$ for all $j \in Z$ where $Z$ denotes the set of integers.
5
votes
0answers
1k views

Optimized way to compute L1 distance matrix

I'm computing distances between two groups of multi-dimensional points giving a matrix of distances pairwise between points. For the L2 (euclidean) distance I can use optimized matrix multiplication ...
5
votes
0answers
340 views

numerical linear algebra tricks for repeated sums and inversions with symmetric positive-definite matrices

I'm doing the following procedure to get the max-likelihood estimate of a matrix-variate normal distribution from $r$ samples of matrices in $\mathbb{R}^{n \times p}$ (algorithm from Dutilleul (1999)):...
4
votes
0answers
54 views

Gram-Schmidt: how close are resulting vectors to $0$?

Let $\{u_1,u_2,\ldots,u_n\}$ be the orthogonal (i.e., before the normalization) basis obtained from linearly independent vectors $\{v_1,v_2,\ldots,v_n\}$ by the Gram-Schmidt process, starting from $...
4
votes
0answers
102 views

Least square problem constrained to projection matrices

Some times in engineering, it is important to find an optimum subspace in which projecting on it satisfies some properties. Let known matrices $A$ and $B$ belong to $\mathbb{R}^{p\times n}$ and $\|\...
4
votes
0answers
84 views

Fast algorithm for sum of absolute eigenvalues

Given a non-selfadjoint real or complex $n\times n$ matrix $A$ with eigenvalues $\lambda_1,\dots,\lambda_n\in\mathbb C$, is there a (faster) algorithm for computing $$\sum_i\lvert\lambda_i\rvert$$ ...
4
votes
0answers
184 views

Eigenvalue problem with symmetric matrix with diagonal diagonal blocks

I would like to efficiently compute all the eigenvalues and eigenvectors of a real matrix A for which the structure is as follows: $A =\begin{bmatrix} D_1 & C\\C^T & D_2 \end{bmatrix}$ , in ...
4
votes
0answers
657 views

Leverage points in linear regression

From the wikipedia, leverage of a point is defined as the measure of how far away the independent variable values of an observation are from those of the other observations. Mathematically for point(...
4
votes
0answers
71 views

How should I interpret the angle between a true solution (function) and a finite element vector solution?

Within the context of elliptic PDEs, I am having difficulty understanding how to quantify the "angle" between the true solution (a function defined over the domain) and the associated finite element ...
4
votes
0answers
248 views

Solving linear equations with block structure and weak coupling

I have a standard set of linear equations $Ax=b$ where the Hessian matrix $A$ has the special block structure as shown: $A= \begin{pmatrix} T & U\\ U^T & V \end{pmatrix}$, $x= \begin{...
4
votes
0answers
199 views

Iterative methods: What happens when the spectral radius of a matrix is exactly 1?

I know that an iterative method (I'm using Jacobi and Gauss-Seidel in this case) will converge iff the spectral radius (max absolute value of eigenvalues) of its iterative matrix is strictly less than ...
4
votes
0answers
2k views

What does affine invariance mean in the context of the Newton's method?

The textbook Numerical Solution of Boundary Value Problems for Ordinary Differential Equations (by Ascher, Mattheij, and Russell) states on page 329: [W]e observe that Newton's method is affine ...
4
votes
0answers
81 views

Does anyone know any reference for this matrix?

For $n \geq 4$, $A$ is $(n-1) \times (n-1)$ tridiagonal block matrix $$A = n^2 \begin{bmatrix}B & -I & 0 & \cdots & \\-I & B & -I & 0 & \\ 0 & -I & B & -I ...
4
votes
0answers
137 views

Find the eigenvector with maximum overlap

Given a large symmetric matrix $A$, there are methods to find the largest or smaller eigenvalue, or the eigenvalue closest to some initial value. Is there any method to find the normalized ...
4
votes
0answers
94 views

Conditions of a Monotonic Process?

$f$ is the output of a discrete time process described by $f(k)=\sum\limits_{i=1}^{k-1}w_{ki}f(i)$ where $f(1)\geq0$ is a known initial condition and $w_{ki}\geq0$ are weights of previous states on ...
4
votes
0answers
439 views

Inverse of Sum of Matrix Inverses

Given $N$ positive-definite matrices $\Lambda_i$, I need to efficiently compute $\Gamma_N$, where $$ \Gamma_n = \left(\sum_{i=1}^n \Lambda_i^{-1}\right)^{-1}. $$ Applying the Woodbury matrix identity ...
4
votes
0answers
150 views

What is the significance of the matrix in the LAPACK logo?

This is the LAPACK linear algebra library logo: What is the significance of this matrix?
4
votes
0answers
2k views

Why is Cholesky factorization numerically stable

It's often stated (eg: in Numerical Recipes in C) that Cholesky factorization is numerically stable even without column pivoting, unlike LU decomposition, which usually need pivoting schemes. But I'...
3
votes
0answers
56 views

Best method to calculate the characteristic polynomial

Is there a "gold" standard for computing the characteristic polynomial of a given $n \times n$ matrix in finite precision arithmetic on a computer? There are fast methods running in $O(n^3)$ or even $...
3
votes
0answers
280 views

Woodbury Matrix Inversion

I am trying to invert a matrix using Woodbury identity. The inversion using Cholesky decomposition has the following pseudo-code: For $t=1,2,...$ $(1)\;\; \text{Read}\;x_t\in\mathbb{R}^n$ ...
3
votes
0answers
41 views

Solving an inequality containing Legendre polynomials

Let it be given that $A$ is a real valued $m$ by $n$ matrix with entries $p_j\left(\frac{i}{m-1}\right)_{i,j=0}^{m-1,n-1}$, where $p_j$ is a Legendre polynomial. Show that $$\frac{\|{x}\|_2}{2} \leq \...
3
votes
0answers
57 views

Cholesky of a submatrix

I have a large-ish matrix that is the Kronecker product of two smaller matrices $V = A \otimes B$. A and B are both positive definite. I want to take the Cholesky decomposition of arbitrary subsets ...
3
votes
0answers
86 views

Binary eigenvalues matrices and continued fractions

I'm working on a rational approximation of the square root function by continued fractions in the complex plane. The following kind binomial coefficients Hurwitz matrices (for $n=4$ and $6$) play ...
3
votes
0answers
72 views

Have you seen this “exponent of matrices” before?

No, not that matrix exponential. Given an $n \times m$ matrix $A$ and an $n \times k$ matrix’s $B$ define their “funky exponent” $B^A$, an $m \times k$ matrix, entrywise by $$(B^A)_{ij} := \prod_{z = ...
3
votes
0answers
279 views

Given overdetermined system $Ax=b$, how can we compute $c^T\hat{x}$?

I have an overdetermined system $$Ax=b$$ where $A \in \mathbb{R}^{m \times n}$ has full column rank and $b \in \mathbb{R}^{m}$. Let $\hat{x}$ denote the least squares solution. If am given $c \in ...
3
votes
0answers
119 views

A new way to generate Triangular Numbers…interesting?

An open ended question... In my work in aerodynamics, lifting line theory specifically, there is a matrix $Q$ that relates vortex strength to wing downwash. While fiddling with the problem and ...
3
votes
0answers
45 views

Help understand why this proof can be “easily extend” while it uses a property specific to 2-norm.

Given the standard inner product $〈\cdot〉$, the $\bf W$ norm for some matrix $\bf W$ is defined as $〈{\bf x},{\bf y}〉_{\bf W}=〈{\bf Wx},{\bf y}〉$. Given an iteration ${{\mathbf{x}}^{i + 1}} = {{\...
3
votes
0answers
48 views

QR decomposition with different metric

I want to find a QR decomposition of a matrix $\mathbf{C} = \mathbf{QR}$ but with the condition that $\mathbf{Q}^{\dagger}\mathbf{S}\mathbf{Q} = \mathbf{I}$, where $\mathbf{S}$ is some general metric. ...
3
votes
0answers
25 views

preconditioners for matrices arising out of PDEs

Suppose I have the heat the following one dimensional PDE for the heat equation: $$ \frac{\partial u}{\partial t } = \alpha \frac{\partial^2 u}{\partial t^2 } $$ which I discretized in the spatial ...
3
votes
0answers
152 views

Condition number of preconditioned regularization problem involving Kronecker Product

Situation I have some results from applying right-preconditioned CGLS to the damped normal equations $(A^TA + \alpha^2I)\ \mathbf{x}=A^T\mathbf{b}$. I'm trying to find the condition numbers of the ...
3
votes
0answers
34 views

Optimization when most entries of the matrix are already fixed?

The question is to optimize $\min_{\bf{P}}\left\| {{\bf P}^{\text{T}} \bf{AP}}-\bf{B} \right\|_F$ where ${\left\| \cdot \right\|_F}$ is the Frobenius norm, ${\bf{A}},{\bf{B}}$ are any two matrices ...
3
votes
0answers
1k views

QR factorization: Givens rotations vs. Householder reflections

Here is the algorithm for Housholder $QR$ factorization: $A$ is a $m \times n$ matrix and $m$ is greater than $n$. $For \quad k=1 \quad to \quad n$ $\quad x = A_{k:m,k}$ $\quad v_{k} = sign(x_{1})|...
3
votes
0answers
132 views

lower bound on the norm of Hadamard product

Suppose $A \in \mathbb{R}^{n \times n}$ is a nonsingular matrix, $D_1, D_2 \in \mathbb{R}^{n \times n}$ are both diagonal matrices with decreasing positive real values on the diagonals. Can you ...
3
votes
0answers
122 views

Efficient way to rigorously learn AI prerequisites

Question: My formal goal is to be able to rigorously understand the mathematical basis for modern statistical learning methods (ML, deep learning). I am told by math people that this involves: linear ...
3
votes
0answers
70 views

Upperbound of the ratio of column sums of an integer matrix

Suppose $X_{n \times n}$ is a positive integer matrix where $n\geq 2$. The element in the $i_{th}$ row and $j_{th}$ column of the matrix $X$ is defined as $x_{i,j}$. Now, consider $S_{j,j+1}=argmax_{...
3
votes
0answers
4k views

Number of Arithmetic Operations in Gaussian-elimination/Gauss-Jordan Hybrid Method for Solving Linear Systems

I am stucked at this problem from the book Numerical Analysis 8-th Edition (Burden) (Exercise 6.1.16) : Consider the following Gaussian-elimination/Gauss-Jordan hybrid method for solving linear ...
3
votes
0answers
106 views

How do I apply this PDE as an image filter?

I'm trying to preprocess a height map image with a helmholtz-type equation as described in this paper. The equation is: $$ddx(h') + ddy(h') + y(h'-h) = 0$$ I solved for h and got: $$\dfrac{ddx(h')}{...
3
votes
0answers
185 views

Express Lagrange polynomial in term of Cauchy matrix

Given 2n distinct real numers $s_1,s_2, \dots, s_n$ and $t_1, t_2, \dots,t_n$ define the $n \times n$ Cauchy matrix $C = C(t,s)$ by $C_{ij} = \frac{1}{t_i - s_j}$. Express the Lagrange interpolation ...
3
votes
0answers
80 views

Can the Lanczos algorithm converge very fast by taking a good initial guess?

Suppose I have the two lowest eigenvectors $v_1$, $v_2$ of a matrix $M$. If slightly change $M$ to $M'$. Can I use $v_1$ or $v_2$ as an initial guess for $M'$? If so, which one should be used, $v_1$ ...
3
votes
0answers
128 views

Lagrange multiplier for more than one constraints.

How to minimize $x^TAx$ over the set $D=(x\geq 0, x^TBx=1$ and $(I-A^\dagger A)x=0$), where $A$ is copositive matrix of order $n-1$ and $B$ is strictly copositive matrix of order $n$. If I drop the ...
3
votes
0answers
141 views

Effective computation of matrix commutator

Is there a faster way to compute the commutator of large (at least one of them sparse) matrices $[A,B]$ then to compute $AB$ ,$BA$ and subtract them?
3
votes
0answers
681 views

Standard algorithm for symmetric tridiagonal matrix eigendecomposition?

Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm. I need to code this on C++ for my personal project. This algorithm involves the eigendecomposition of ...