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

learn more… | top users | synonyms

5
votes
2answers
336 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 ...
4
votes
1answer
176 views

solution to $\min \|A-BXC \|$

I have the following problem. Let $A$, $B$ $C$ be real-valued matrices of size $m \times q$, $m \times n$, $p\times q$ respectively. I would like to find matrix $X$ of size $n\times p$ and maximum ...
1
vote
2answers
113 views

Calculate sum of ONB

Here's a homework question: Let ${u_1, \ldots, u_n}$ be an ONB in $C^n$. Assuming that $n$ is even, compute $$||u_1 - u_2 + u_3 -\cdots - u_n||$$ I have no idea how to solve this. Can anyone help? ...
1
vote
0answers
56 views

formulas for exact values of singular values in low dimension?

Are there formulas for the singular values of a real matrix in low dimension, i.e. for a $2 \times 2$ matrix or a $2 \times 3$ matrix? Any comment is welcome.
0
votes
1answer
252 views

Norm $\|A\|$ is not induced by any vector norm [duplicate]

Possible Duplicate: Subordinate matrix norm I have a question in my homework for Numerical Linear Algebra, which is as follows: Show that the norm $\|A\| = \max \limits_{i, j} |a_{i,j}|$ ...
10
votes
2answers
1k 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: ...
1
vote
0answers
150 views

The fastest algorithm of computing Principal eigenvector of a non-negative-entries matrix

I am studying the QR algorithm, is it the fastest one in this situation?
0
votes
1answer
566 views

Could explain me how eigenvector helps with compute gradient and how make differentiate operation on decrete space like digital image?

Could you explain me how eigenvector helps with compute gradient and how make differentiate operation on descrete space like digital image? I know that this question is so connected with computer ...
8
votes
1answer
2k 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 ...
3
votes
2answers
164 views

Fast inversion of a triangular matrix

I need to inverse a matrix $A$ given its $QR$ decomposition. It's a numerical task. It is told that the inversion should be "possibly cheap". But it does not look like I can do something more ...
1
vote
0answers
145 views

Stable and efficient projection onto subspace along another subspace

Suppose we are given the euclidean space $\mathbb R^{n+m}$ with the decompositin $\mathbb R^n = V \oplus W$, which we however do not expect to be orthogonal. Let us describe the matrix $P$ that ...
0
votes
1answer
135 views

If $A$ is Symmetric Positive Definite(SPD) matrix, is $A+E$ SPD?

Let $A$ be symmetric positive definite matrix and $E$ is symmetric with $||E||_{2} < ||A^{-1}||^{-1}_{2}$ then prove that $A+E$ is symmetric positive definite. -- \ Observation; Since $A$ is ...
-1
votes
2answers
1k views

Library for Jacobi eigenvalue algorithm [closed]

I am looking for a C or C++ or fortran library that implements the Jacobi eigenvalue algorithm: http://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm do you know if it is available?
0
votes
1answer
669 views

LU decomposition with row pivoting

Okay so consider a matrix $$ A = \left( \begin{array}{ccc} 0 & 1 & 1 \\ 1 & -2 & -1 \\ 1 & -1 & 1 \end{array} \right)$$ so obviously to get the upper and lower traiangular ...
2
votes
2answers
1k views

Modified Cholesky factorization and retrieving the usual LT matrix

I have been looking at the modified Cholesky decomposition suggested by the following paper: Schnabel and Eskow, A Revised Modified Cholesky Factorization Algorithm, SIAM J. Optim. 9, pp. 1135-1148 ...
3
votes
0answers
80 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 ...
1
vote
1answer
243 views

LU Decomposition

Can we use partial pivoting when obtaining the upper triangular matrix using Gaussian elimination? If so, how can we do it? Let $Ax=B$ and $A=LU$ To determine $L$, it seems fancy to use pivoting as ...
1
vote
3answers
136 views

Compute $\mathbf v \mathbf A^{-1}\mathbf v^\top$ in a numerically stable way

I've read that you should avoid computing a matrix inverse, as you generally don't need to, but I don't know the best way to avoid it. I need to compute: $$x = \mathbf v \mathbf A^{-1}\mathbf ...
0
votes
2answers
144 views

Superlinear convergence of conjugate gradients

The global convergence bounds of conjugate gradients are too pessimistic, how can the super-linear convergence, experienced in practice, be explained?
4
votes
2answers
81 views

Norm “maintaining” matrices

Let $A$ be an $m\times n$ matrix such that $m < n$. I would like to know the conditions on $A$ such that the following is true: $$\|Ax\| \leq \|Ay\| \implies \|x\| \leq \|y\|$$ It can easily be ...
0
votes
1answer
433 views

QR-algorithm - convergence property

If $A\in \mathbb R^{n \times m}$ and $A = A^\top$ and if $\vert \lambda_1 \vert >\vert \lambda_2 \vert >\cdots>\vert \lambda_n \vert >0$ then $\lim\limits_{k\to \infty} Q_k = I$, ...
0
votes
1answer
56 views

Algorithms for Nonunique Factorizations of a Real Symmetric Matrix

Suppose we have an indefinite real symmetric matrix $P$, of (reduced) rank $\alpha$. Then there is a (nonunique) decomposition of the matrix: $P = YMY'$, where $M = \left[\begin{array}{cc} M_+ ...
0
votes
2answers
621 views

Ill-conditioned matrix [duplicate]

Possible Duplicate: Inverse matrices are close iff matrices are close Consider this problem: $Ax = b$ I want to solve it/find x and the matrix A is ill-conditioned. Why is the fact "A is ...
2
votes
2answers
491 views

Numerical Linear Algebra - Finding the eigenvector associated with a known eigenvalue

I have written a linear solver employing Householder reflections/transformations in ANSI C which solves Ax=b given A and b. I want to use it to find the eigenvector associated with an eigenvalue, like ...
3
votes
1answer
193 views

Testing constrained linear least squares for optimality

I've written a C# solver for linear least squares problems with inequality constraints. That is, given $A$, $b$, $G$, $h$ $$\min\|Ax-b\|^2\text{ s.t. }Gx\ge h$$ I have a few hand crafted test ...
2
votes
0answers
167 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 ...
4
votes
1answer
562 views

Algorithm for solving sparse equality-constrained least squares

I have a diagonal, positive-definite inner product matrix $M$ and want to find a minimizer of $$\min_q \frac{1}{2} \|q-q_0\|_M^2\qquad \text{s.t.}\qquad C^Tq+c_0 = 0,$$ where $q_0, c_0$, and $C$ are ...
3
votes
1answer
441 views

Eigenvectors of a matrix reduced to tridiagonal

I am implementing an algorithm to calculate eigenvalues and eigenvectors of a symmetric matrix in a GPU. In order to calculate the eigenvalues I first reduced the matrix to the tridiagonal form using ...
2
votes
1answer
160 views

Question on “avoidance of crossing”

In review of linear algebra I come across this phenomenon, the Google Book link is this: What I do not understand is Lax tried to persuade us that "there is another way of parametrizing these ...
5
votes
2answers
585 views

When does an eigenvector of a matrix contain only a constant?

When I compute the eigenvectors of a certain matrix, the first of them is composed entirely of a single constant. What properties of a matrix lead to this result? Update By "a vector composed ...
4
votes
1answer
2k views

Linear least squares with inequality constraints

I'm trying to follow this older paper, page 19. The goal is to solve: $\min \|Ax-b\|^2 s.t. Gx \ge h$ given $A, G, b, h$ By combining the equations into a single LCP of the form: $Mz + q = w$ s.t. ...
3
votes
1answer
240 views

How to Store a Banded Matrix by Diagonal

I'm taking a graduate level independent study course this semester in Matrix Computations. I'm not getting much support from the professor, so am turning to the excellent StackExchange community for ...
1
vote
0answers
148 views

Nonlinear least squares and polygon area

I found this paper that describes preserving the global area of a polygon given some deformation (section 5): http://www.kunzhou.net/publications/2DShape.pdf I'm trying to do something very similar. ...
1
vote
2answers
765 views

Decomposition of a unitary matrix via Householder matrices

If $U$ is unitary, how can I show that there exist $w_{1},w_{2},...,w_{k}\in \mathbb{C}^{n}$, $k\leq n$, and $\theta_{1},\theta_{2},...,\theta_{n}\in \mathbb{R}$ such that $U=U_{w_{1}}U_{w_{2}}\cdots ...
1
vote
1answer
652 views

solving a system of equation by rotation

Somebody hinted that one can solve a system of equations with some method of rotation. This is only needed for numeric solutions, otherwise Gauss-Jordan (RREF) is just fine. What is this rotation ...
5
votes
2answers
299 views

Check whether two subgroup of $GL(n,\mathbb Z)$ are conjugate

Suppose I have two finite subgroups of $GL(n,\mathbb Z)$. Is there an algorithm to find out whether these two belong to the same conjugacy class in $GL(n,\mathbb Z)$? I tried by using the Jordan ...
5
votes
2answers
953 views

Least square principles with Lagrange multiplier

I have a function to minimize: $$f(a_1,a_2,a_3,a_4)=\sum_{i=1}^n\left(\sum_{k=1}^3 a_k\ p_i^k -a_4\right)^2$$ subjected to this constraint: $$a_1^2+a_2^2+a_3^2=1$$ and $$a_4\geq0$$ I am trying ...
7
votes
4answers
1k 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 ...
3
votes
1answer
759 views

Number of FLOPS required to solve Sherman-Morrison formula for matrix inversion

I have the expression for the inversion of a matrix with the Sherman-Morrison formula as follows (given that $A^{-1}$ is known). $$B^{-1} = A^{-1} + ...
1
vote
2answers
322 views

System of linear equations, resulting from a weighted graph. How to solve this numerically?

We have a problem that leads to a system of linear equations which has to be solved numerically. There are thousands of algorithms to solve linear equations, but I haven't found any that fits our ...
2
votes
1answer
104 views

Fast Algorithm For Adding An Equation To A System?

Assume an $N \times N$ matrix $A$ and a length $N$ vector $b$. I've already solved the system $Ax = b$ for $x$ using standard methods. (If you want you can assume that I have the inverse of $A$ as ...
1
vote
0answers
74 views

Looking for a specific paper not available electronically

not really sure that it is the right place to post, but I'll give it a go. I really would love to have a look to this technical report J.G. Lewis, Algorithms for Sparse Matrix Eigenvalue Problems, ...
3
votes
3answers
415 views

Optimizing Cholesky factorization for multiple sparse matrices with same nonzero pattern

I'm using a Cholesky factorization to solve the linear step in a nonlinear system of equations (nonlinear finite element analysis). In the PETSc library, one can specify a parameter for ...
2
votes
2answers
2k views

Exact Computational Costs/Flop count for algorithms

I need exact computational costs for different algorithms to benchmark a code. For instance, the exact cost of Gauss Elimination is given here. I am not interested just in the leading order term. The ...
1
vote
0answers
103 views

Fast simultaneous orthonormal basis computation for multiple nullspaces

Consider vectors $a_i\in R^{m\times n}$ and $B\in R^{m\times p}$, with $n +p < m$, and assume that the columns of $(A, B)$ are linearly independent. To compute an orthobasis for $\text{ker}(A)$, it ...
0
votes
1answer
463 views

computing Moore-Penrose pseudoinverse when SVD computation does not converge

I am writing a routine to return the Moore-Penrose inverse of a rectangular matrix. Currently am computing the Moore-Penrose inverse using SVD, i.e., if the SVD is given by $A = \sum_{i=1}^r ...
2
votes
1answer
102 views

Computing Singular Value question

Good afternoon. I'm studying for my finals of this year, currently studying for the exam "Numerical Linear Algebra". I'm trying to solve some of the questions the teacher asked the past years (for ...
12
votes
3answers
499 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 of the matrix itself. It is of central importance in Signal Processing and ...
2
votes
0answers
918 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 ...
2
votes
1answer
255 views

PCA for data compression

I would like to use PCA (Principal Component Analysis) to compress a sequence of vectors, $v_0 \ldots v_n$. My plan is to concatenate these vectors into a matrix: $M = [ v_0 \ldots v_n ]$ I will ...