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

learn more… | top users | synonyms

6
votes
0answers
253 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
74 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
151 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
73 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
360 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 ...
3
votes
0answers
47 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
46 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 ...
3
votes
0answers
63 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
65 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
358 views

Trace Minimization of Covariance Matrix

Given a matrix X whose rows contain observations collected at some locations. Can someone explain how trace minimization of covariance matrix $XX^T$ can lead to orthogonal / mutually independent ...
3
votes
0answers
412 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
598 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
78 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
474 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
36 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
112 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
46 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
30 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
41 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
44 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
55 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
22 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
75 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
93 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
58 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
57 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
74 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
40 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
49 views

Customising force-directed graph layout

I would like to implement a variant of the force-directed graph layout where some nodes are constrained to moving only along a predefined curve (e. g. circle). I looked at some implementations using ...
2
votes
0answers
123 views

Orthonormal Matrix weighted regression

$Q$ is a rectangular matrix with orthonormal columns. A linear system composed of $$Qx= b$$ is really easy to solve as: $$Q'Q=I$$ hence: $$x=Q'b$$ Given that $Q$ is orthonormal can this be used to ...
2
votes
0answers
118 views

$l^1$ norm estimate for inverse of Vandermonde matrix

As title, I would like to know the known upper bound for the $l^1$ norm for inverse of Vandermonde matrix. A quick search gives this paper by Gautschi 40 years ago, but it deals with the infinity norm ...
2
votes
0answers
53 views

Solution to pertubed linear system

Suppose one has the following system of linear equations $$(A + \Delta A) x = b$$ where $A$ and $\Delta A$ are large sparse matrices and $\Delta A$ is "small" compared to $A$, furthermore vector $x$ ...
2
votes
0answers
144 views

Showing that the least-square method minimizes error

Assume that the relation between temperature and time is defined as follows: $$T = A^kC$$ We can find parameters $A$ and $C$ using the least-square method. The given relation is not linear, but we can ...
2
votes
0answers
41 views

commuting a LU factorisation

Consider the permutation matrix $P= \begin{pmatrix} 0 & \cdots & 0 & 1 \\ 0 & \cdots & 1 &0 \\ \vdots & \ddots & \vdots & \vdots \\ 1 & \cdots ...
2
votes
0answers
123 views

Check for Ill Conditioned matrix

How can I efficiently check if a tridiagonal system with 1's in diagonal is ill-conditioned or not ? The common way is to get the ratio of largest and smallest singular values and see if its greater ...
2
votes
0answers
87 views

QR decomposition help

What do Q and R stand for? Why must the diagonal entries of R be positive instead of just nonzero?
2
votes
0answers
25 views

Re-calculate solution after altering some elements in a linear system

Problem I have a linear system: $$ Mx = b $$ $M$ is like a Band Matrix. And assume I have a solution $x_{init}$ at beginning. There will be some operations which are going to alter some elements in ...
2
votes
0answers
76 views

Spectral/ Eigen-Value solution with a linear constraint?

Is there a spectral or eigen-value solution to finding $X$ such that $Tr(CX^TMX)$ is minimum for a symmetric matrix $C$ and a p.s.d matrix $M$. Also there is a linear constraint on the minimization ...
2
votes
0answers
132 views

The norm of the matrix

This problem is in Trefethen'book Numerical Linear Algebra Suppose the $m\times n$ matrix $A$ has the form $A=\begin{pmatrix}A_1\\A_2 \end{pmatrix}$ where $A_1$ is a nonsingular matrix of dimension ...
2
votes
0answers
85 views

Need little hint to prove a theorem .

I have an iterative method \begin{eqnarray} X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots \end{eqnarray} with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
2
votes
0answers
2k views

What is the algorithm for LU factorization in MATLAB?

What is the algorithm for LU factorization in MATLAB, i.e. [L,U] = lu(a)? After searching for many examples and trying to compare the result with MATLAB, they are ...
2
votes
0answers
140 views

(Experimental) Can it be shown that this extension of the secant-interpolation has quadratic convergence?

Background: I needed some efficient but simple interpolation-methods aside of Newton's iteration because I want to have it in contexts, where the derivative of a function is not always known. So an ...
2
votes
0answers
679 views

QR with column pivoting

Golub and van Loan's algorithm 5.4.1 for QR factorization is suitable as a rank revealing algorithm. The results are R, Q with the subdiagonal elements stored in "factored form" and the column ...
1
vote
0answers
25 views

Iterative methods for solving a linear equation system

There are several methods known for solving a linear equation system Ax = b (like Jacobi or Gauss-Seidel) by iterating $x_{n+1}=Mx_n+c$ with a matrix M, for which some norm is smaller than 1. But ...
1
vote
0answers
18 views

About reduction to Hessenberg matrix

I've read somewhere that Hessenberg decomposition is not unique unless the first column of $Q$ is given. i.e $Q^TAQ=H$ Then I read the algorithm of Arnoldi iteration and I found an amazing fact: ...
1
vote
0answers
23 views

Solving tridiagonal matrices where the top left element is zero

If I have a matrix like this: $$ \left[\begin{array}{rrrrrrrrr|r} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & ...
1
vote
0answers
37 views

Numerical rounding errors in intersection code

I hope this question is in the right place, as it is as much about programming as it is about math. I'm trying to find the intersection between a circle and a line. My implementation of the algorithm ...
1
vote
0answers
22 views

Gaussian elimination vs. Jacobi iteration

How can I determine which of the matrix solver is faster for a given set of equations: Gaussian elimination or Jacobi iteration? In case, I have a banded matrix, is it advisable to use LU ...
1
vote
0answers
26 views

When is the LU decomposition unique?

I want to find out when a matrix decomposition $A = LU $ (L lower and U upper matrix) is unique? Clearly, if $A$ is not invertible, there is no chance that this decomposition is unique. Hence, ...
1
vote
0answers
18 views

Check feasibility of a system of integer linear equations

I'm currently working on a very large integer linear programme which cannot be solved within any reasonable time. The initial set of linear equations S={Ax<=b) is feasible. I want to add more ...