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

learn more… | top users | synonyms

7
votes
0answers
67 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
327 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 ...
5
votes
0answers
85 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? ...
5
votes
0answers
211 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 ...
5
votes
0answers
455 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 ...
5
votes
0answers
86 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 ...
4
votes
0answers
39 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
63 views

Conditions of a Monotonic Process?

$f$ is the output of a discrete time process described by $f(k)=\sum_{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 the ...
4
votes
0answers
743 views

General properties of eigenvalues of a Jacobian matrix when premultiplied by a symmetric, positive definite matrix?

For a particular engineering problem that I'm working on, I have computed a Jacobian matrix $J$ and there is another matrix $M$ associated with the problem. $M$ is known to be symmetric, real-valued, ...
3
votes
0answers
69 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: ...
3
votes
0answers
59 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 ...
3
votes
0answers
121 views

Difference between Householder Reflections and Gram-Schmidt?

In numerical QR decomposition, when we calculate the orthonormal factor Q of a matrix, what is the difference in results if we use Householder Reflections to normalize the matrix or use Gram-Schmidt ...
3
votes
0answers
90 views

Solver for sparse linearly-constrained non-linear least-squares

Reposted from stackoverflow on the advice of Nick Rosencrantz: Are there any algorithms or solvers for solving non-linear least-squares problems where the jacobian is known to always be sparse, and ...
3
votes
0answers
700 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 ...
3
votes
0answers
81 views

What's the state of the art for computing the largest singular value of a matrix

My matrix is not sparse, and is sized 30k by 30k. Most importantly, the gap between the largest and the second largest singular values is small or even 0. ARPACK, SLEPc, Matlab, PROPACK? Which ...
3
votes
0answers
519 views

Numerical methods to find eigenvectors with 0 eigenvalue

I'm curious if there's any numerical way of directly finding the eigenvectors with eigenvalue 0. If I didn't have to do it directly, I would probably do it like this in pseudocode: ...
2
votes
0answers
54 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 ...
2
votes
0answers
51 views

Fastest way to find linearly independent columns of a matrix

Given a rectangular matrix $X$ of size $n\times m$ with $m>n$, what is the fastest way to find the linearly independent coloums. Robust methods like SVD or RRQR decompostion have complexity of ...
2
votes
0answers
18 views

Reference request for finite difference method

I am trying to use finite difference method to solve the minimizing problem $$ J[u]=\min_{u\in BV(Q)}\{\|u-f\|_{L^1(Q)}+|u|_{BV(Q)}\} $$ where $Q=(0,1)\times (0,1)$ is a uint square and ...
2
votes
0answers
42 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.
2
votes
0answers
36 views

Nearest non-negative solution for $Av=b$

Let $A$ be a $n\times m$ matrix. Let us define the system $$Av=b$$ $$v\geq 0$$ I want to find a solution $v$ of this system that is the closest (euclidean norm) to $v_0$, a given $n$-dimensional ...
2
votes
0answers
91 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 ...
2
votes
0answers
19 views

Dense Rank Deficient Linear System

What are some of the best methods for solving a Dense Rank Deficient Linear System $Ax = b$, where $A$ is Dense, Symmetric but possibly Rank Deficient. I know SVD can solve it pretty nicely while ...
2
votes
0answers
61 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) ...
2
votes
0answers
44 views

Solving a structured partitioned linear system

I am trying to solve the following partitioned linear system, where each letter represents a block $\begin{pmatrix}-H & A^T & I_n \\ A & 0_1 & 0_2 \\ z_D & 0_2^T & ...
2
votes
0answers
43 views

Wiedemann for solving sparse linear equation

I am new member. I am researching in Wiedemann algorithm to find solution $x$ of $$Ax=b$$ Firstly, I will show a Wiedemann's deterministic algorithm (Algorithm 2 in paper Compute $A^ib$ for ...
2
votes
0answers
49 views

Find the solution of linear equation using Wiedemann/ Krylov method

I am using Wiedemann (some literature called Krylov method) to find the solution of a linear equation that defined as $$Mx=b$$ Instead of resolving entire elements of x (size $K \times 1$), we can ...
2
votes
0answers
36 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$ ...
2
votes
0answers
150 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 ...
2
votes
0answers
43 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 ...
2
votes
0answers
70 views

Numerically approximate the maximum of an element of a vector after a series of matrix multiplications.

Where S is a sigmoidal function, A_i is a matrix, and x is an input vector, and ...
2
votes
0answers
73 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?
2
votes
0answers
76 views

Best way to solve specific block-tridiagonal linear system (10000x10000 and larger)

To provide more context, this system came from energy balance equation on a mesh with (n,m) nodes in each direction. It's a linear system that looks like this (size of system in blocks n = 4, size of ...
2
votes
0answers
236 views

Standard symmetric tridiagonal matrix Eigenvalue decomposition algorithm?

Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm (here). I need to code this on C++ for my personal project. This algorithm involves the eigenvalue ...
2
votes
0answers
63 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
2
votes
0answers
35 views

Smallest set of Liner equations, which exactly fit a set of points

I have a set of 2-d points,(it can be of any arbitrary dimension n). I want to find the minimum set of straight lines(linear equations) which exactly passes through the given 2-d points (unlike ...
2
votes
0answers
158 views

Inverse of the sum of a symmetric and diagonal matrices

I have two square matrices, $A$ and $B$. $A$ is a block symmetric matrix with 1's along the diagonal (and therefore 1's in whole blocks along the diagonal). $B$ is diagonal, with the same block ...
2
votes
0answers
55 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 ...
2
votes
0answers
49 views

linear algebra formulation help

I asked this on mathoverflow as well and apologies for cross-posting. I am trying to compute this so-called bending energy matrix. The bending energy of a thin plate in 3D is given by: $$ BE = ...
2
votes
0answers
108 views

Finding generalized eigenvalues with linear constraints

I have a generalized eigenvalue problem $$Mx = \lambda Bx$$ with the additional constraint that $Cx=0$, where $M$ and $B$ are positive-definite and $C$ is a sparse and rectangular. Is there a simple ...
2
votes
0answers
24 views

Nontrivial Matrix-estimate

I try to proof the following estimate: \begin{align} h' W^{-1} H W^{-1} h \geq c h' H h \qquad c>0, \qquad\qquad (1) \end{align} where $h\in\mathbb{R}^{K-1}$ and ...
2
votes
0answers
159 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 ...
2
votes
0answers
151 views

How to generate a random matrix which have given singular values?

I know one method: generate a random matrix, apply SVD decomposition, modify singular values, and then multiply those matrices back together. However, I'm wondering how random this method is. Since ...
2
votes
0answers
70 views

Inverses of the sums of all possible subsets of a set of symmetric and positive definite matrices

I have a set of $c$ matrices $A_1 ... A_c$ which are all symmetric and positive definite. I would like to calculate the inverses of all the possible sums, i.e. ...
2
votes
0answers
875 views

Least Squares “analytic expression” for fitting a 2D quadratic function to measurements

I have n scattered elevation measurements: $ \{x_i,y_i,z_i\}_{i=1..n} $ that I want to fit a quadratic function to: $ z = ax^2 + by^2 + cxy + dx + ey + f$. The problem can be written as a vector ...
2
votes
0answers
73 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?
2
votes
0answers
649 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}= ...
2
votes
0answers
103 views

Determinant error bound is better than norm bound for matrix product

In by textbook on numerical algebra, it states that for a numerical matrix product the error bound: $|A B - \hat{A} \hat{B}| \le c|A| |B|$ is a stronger expression than $\|A B - \hat{A} ...
2
votes
0answers
50 views

maximal m-elements of the matrix inversion

Suppose the $n\times n$ matrix $A$ is invertible, and all its elements are between 0 and 1. The existing matrix inversion operation of $A^{-1}$ will take $O(n^3)$ time. Now I just want to find the ...
2
votes
0answers
142 views

Nearest point to a convex polytope

I am looking for fast, memory-efficient computational algorithms to solve the following problem: Minimize: $||x - x*||_2^2$, subject to constraints $A x = a, B x <= b, l <= x <= u$, where ...