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

learn more… | top users | synonyms

1
vote
0answers
608 views

Multigrid Interpolation and Restriction operators

I have a question about the restriction and the interpolation operators of a Multigrid algorithm. Let those be given: The full weighting restriction stencil (in 2D): $\frac{1}{16} \left[ \begin{...
1
vote
0answers
64 views

Preconditioning and effects on precision of solution of LSE

In my courses on numerical analysis I have been tought that the main and principle motivation for preconditioning linear systems of equations is to increase the convergence rate of iterative solvers ...
1
vote
0answers
324 views

Criterion for detecting rank-deficiency via QR decomposition?

I apologize in advance if this is an ill-posed question -- I'd appreciate advice on what pieces are missing as much as an answer. I'm solving a system like $P \approx X Y^T$, where P is a large ...
1
vote
0answers
365 views

Weighted linear least squares parameter covariance

I am currently trying to figure out the parameter covariance for a weighted linear least squares problem where $$y = X\beta$$ The parameters for which my objective function is lowest are given by $$\...
1
vote
0answers
22 views

How to construct an optimal subspace with 3 indices.

I have a 3-dimensional array that is potentially very large and I need to do quite a lot of operations with it. Is there a systematic way to choose a subspace of a certain size, such that the norm (...
1
vote
0answers
507 views

covariance matrix eigenvalues eigenvectors

Is there a probabilistic or analytical meaning of the eigenvalues/eigenvectors of covariance matrix of multivariate normal distribution? Thank you
1
vote
0answers
174 views

Can antiunitary symmetry be used to calculate determinant of a matrix

Suppose I have some $N \times N$ complex matrix $A$, that commutes with some antiunitary operator $U$ that satisfies $U^2 =-1$. It can be shown that $\det(A)\ge 0$ , because for every eigenvector $v$...
1
vote
0answers
51 views

Numerical linear algebra spectral norm limit.

Let $A \in \mathbb{R}^{m \times n}$ be of full rank. Consider $X_{k+1}=(2k-X_{k}A)X_{k}$, $X_0 = \alpha A^{T}$. Let $E_k = I-X_kA$, Deduce that if $||E_{0} ||_{2}<1$, then $lim_{k \rightarrow \...
1
vote
0answers
161 views

fixed point spectral radius

We have the following stationary matrix iteration $$x_{k+1} = Mx_k + c$$ where $M$ is nxn matrix and $c$ is a vector. Let $r(M)$ denote the spectral radius of $M$. Show that spectral radius $r(...
1
vote
0answers
229 views

Numerical Linear Algebra problem (QR factorization with column pivoting)

For matrices that might be rank deficient it is common to incorporate pivoting in Householder QR factorization of A $\in$ $\Re^{mxn}$ (m $\geq$ n). Let $A^{(k)}$ denote the matrix at the start of the ...
1
vote
0answers
157 views

Show that its a Generalized Eigenvalue problem

Show that the minimizer is obtained by a generalized eigenvalue problem. $$\alpha=\underset{1^TK\alpha=0; \ \alpha^TK^2\alpha=1}{\text {arg min}} \gamma ||f||_{K}^2+f^TLf$$ Details: $K$ is a ...
1
vote
0answers
55 views

Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability

I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
1
vote
0answers
360 views

Finding a row permutation that makes a matrix more “blocks-like”

Disclaimer: what follows arise in a context from Computer Science, but it seems to me that my questions were more likely to be solved from mathematicians than from computer scientists. Let suppose ...
1
vote
0answers
377 views

Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $$F(x) = \sum_{i=1}^{M}\left\|x_{i+1} - x_i - K\left(\frac{x_{i+1} + x_i}{2}\right)\right\|^2 + \|x_1-c_1\|^2 + \|x_N-c_2\|^2,$$ where $x$ is a vector of $N$ scalars, ...
1
vote
0answers
103 views

How to solve Rayleigh Quotient type problem?

How to solve Rayleigh Quotient type problem? $$\max (w+w_0)^tC(w+w_0) \text{ s.t. } w'w=1,$$ where $w_0$ is given. Thank you!
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.
1
vote
0answers
158 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?
1
vote
0answers
172 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 ...
1
vote
0answers
170 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
0answers
76 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, ...
1
vote
0answers
108 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 ...
1
vote
0answers
499 views

Tridiagonal sparse matrix - linear equation

I have to following linear system to solve : $Ax=e_1$ where $A$ is a sparse tridiagonal matrix with the main diagonal terms $a_{ii}$ being all different, and the off-diagonal terms being each others ...
0
votes
0answers
24 views

Linear regression of matrix elements to get the minimal polynomial to perform a matrix inversion?

So each matrix $\bf A$ fulfils an equation for it's minimal polynomial $P_m({\bf A})$: $$P_m({\bf A}) = 0 \Leftrightarrow \sum_{k=0}^{k_n}c_k{\bf A}^k = 0$$ We can by multiplying with $A^{-1}$ and ...
0
votes
0answers
20 views

Singular value decomposition: does the choice of eigenvectors matter?

I'm trying to calculate the SVD-decomposition of a certain matrix, i.e. $ A = U \Sigma V^T$. My solution doesn't yield $A$ again; I just can't get the signs correct. I'm wondering if this is just a ...
0
votes
0answers
14 views

Machine Learning : Proof of equality

currently, I am writing on a paper that also makes use of machine learning techniques. My problem is as follows: I have binary classificator $h_w(\vec{x}^{(i)})$ that simply uses the sigmoid function, ...
0
votes
0answers
41 views

Detail in the shifted QR iteration algorithm

In one explanation of the shifted QR iteration algorithm I've read (p. 537 of "Matrix Analysis and Applied Linear Algebra"), the following proposition is given (without proof): At each step of the ...
0
votes
0answers
29 views

Workability of linear equation solving methods for different fields?

So far, I have mostly done linear algebra over $\mathbb R$ and $\mathbb{C}$. I know there exist very many methods to solve equation systems for those fields, of which a few are Gaussian Elimination, ...
0
votes
0answers
14 views

Why Gauss-Seidel iteration is a projection method

Yousef Saad's iterative method for sparse linear systems says Jacobi, GS, SOR are all projection methods. for example GS is a projection method with $\mathcal K= \mathcal L =\{e_i\}$ (project on $\...
0
votes
0answers
25 views

Complex, symmetric linear equations

What is the fastest numerical method to accurately solve complex, symmetric linear equations? Preferably, with a link to a Fortran code. The dimension is about 100-200 variables. To be more explicit, ...
0
votes
0answers
69 views

What is the fastest known algorithm for finding eigenvalues?

What is the fastest known algorithm for finding eigenvalues? Second and third fast are also of interest if they are simpler, basically anything better than the standard solve characteristic polynomial ...
0
votes
0answers
33 views

Question on SVD Uniqueness Proof

I have problem understanding the proof of uniqueness for SVD by by Trefethen & Bau. If the lengths of the semi-axes of the hyper-ellipse are distinct, then semi-axes themselves are ...
0
votes
0answers
43 views

Linear system equations

I need to get, preferably by a numerical method, a solutions of: $$\left\{\begin{array}{lll} 2\sum_{i=1}^n b_{ik}x_i+x_{n+1}=0&\text{for}& k=1,2\ldots,n\\ \sum_{i=1}^n x_i=0 \end{array}\right.$...
0
votes
0answers
26 views

Query about the Moore Penrose pseudoinverse method

I have recently discovered the Moore-Penrose psuedoinverse method, and I am currently testing the waters with it. I noticed if I have a system, say $$a_1x_1=0$$ $$a_2x_1+a_3x_2=0$$ $$\vdots$$ $$...
0
votes
0answers
41 views

Numerical method for solving equation with $u \frac{\mathrm{d}u}{\mathrm{d}x} + u$

I'm looking for a finite difference method to solve $$a(x) u \frac{\mathrm{d}u}{\mathrm{d}x} + u = b(x)$$ where $u(0) = c$. I tried to do a lagging convergence on the $u$ ie $$a(x) u^{(n)} \frac{\...
0
votes
0answers
20 views

Gauss Seidel - Finite Element Method

I am solving an equation using finite element method, and for that I have to use Gauss Seidel to invert a matrix. In Gauss Seidel I am using a "while" which breaks if the absolute error reaches the ...
0
votes
0answers
16 views

Different ways to leave linearly dependent vectors of a set of vectors

Let a set $S=\left\{ {{\mathbf{v}}_{i}}:i\in \mathbb{Z}_{n}^{+} \right\}$, where $\mathbb{Z}_{n}^{+}=\left\{ 1,2,...,n \right\}$ and ${{\mathbf{v}}_{i}}\in {{\mathbb{R}}^{m}}$ for each $i\in \mathbb{Z}...
0
votes
0answers
25 views

absolute value matrix and derivation of A^1 b

I have a question who could I solve the following sentence? Given is the vector $\vec{b} \in \mathbb{R^n}$ and the function $f : GL(n,\mathbb{R}) \to \mathbb{R}^n$ with $f(A) = A^{-1}b$. Then ...
0
votes
0answers
26 views

Compute the condition number of the matrix and show for what $\Delta x$ it is singular

Given the laplacian $N \times N$ matrix \begin{align*} A=\frac{1}{(\Delta x)^2}\begin{pmatrix} 2&-1& & &\\ -1&2&-1& &\\ &\ddots&\ddots&\ddots&\\ &...
0
votes
0answers
13 views

Determinants using Row Reduction replacement

I am aware replacement does not affect the value of determinant when doing a row reduction. However, I realised there isn't a good explanation on how to handle different forms of replacement when ...
0
votes
0answers
22 views

Given a triangular matrix $T$, can we find an upper bound for $\| |T^{-1}||T|\|$?

Given a triangular matrix $T$, can we find an upper bound for $\| |T^{-1}||T|\|$, where $|T| =|[T_{ij}]| = [|T_{ij}|]$ ?
0
votes
0answers
12 views

Error estimate in iterative refinement for solving a linear system

The iterative refinement can be illustrated as follows: given an approximate solution $\hat{x}$ of the system $Ax = b$, at the $n^{th}$ step of the refinement, $r = b- A\hat{x}^{(n)}$, Solve $Ad^{(n)...
0
votes
0answers
26 views

In practice what is (modified) Gram Schmidt used for?

Modified Gram-Schmidt is known to be numerically less stable than methods like Householder orthogonalization and also not quite as fast at approximately $2mn^2$ flops. So in practice do we ever use it,...
0
votes
0answers
26 views

Finding eigenvectors of the Laplacian operator

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system $\...
0
votes
0answers
35 views

What are useful mappings (operators) in image reconstruction

I'd like to ask the technician mates to provide some information regarding mappings and image reconstruction operators. Please, if possible, provide some articles and helpful discussions about useful ...
0
votes
0answers
13 views

SVD of Cholesky Factor

I am working through the book Fundamentals of Matrix Computations by David Watkins, and I ran into this one and it's stumping me. In my head, I understand the basic premise of it. However, I can't ...
0
votes
0answers
15 views

SVD Transpose Equations

$$Av_i= \begin{cases} \sigma_iu_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m \end{cases}$$ $$A^Tu_i= \begin{cases} \sigma_iv_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m \...
0
votes
0answers
18 views

question about dimensions.

$A\in\mathbb{R}^{n\times n}$, when solving $Ax=b$ numerically in projection method, we approximate the exact solution $x^*$ by $y$ in the subspace $K$ which has the dimension $m$. my textbook said $m$...
0
votes
0answers
27 views

Applications of Khatri-Rao matrices

I'm interested in what applications there are for Khatri-Rao matrices, and in particular for solving linear systems of equations involving Khatri-Rao matrices. A Khatri-Rao matrix is a block matrix ...
0
votes
0answers
23 views

Why does biconjugate gradient (BiCG) work for nonsymmetric matrices?

After looking through the derivation of CG, I understand why it requires the coefficient matrix $A$ to be symmetric, since the property is used to produce a short recurrence relation for the ...
0
votes
0answers
27 views

Simplifying matrix expressions with LU decomposition?

If $A, B, C$ are $n \times n$ matrices, with $B$ and $C$ nonsingular, and $b$ is a vector of size $n$, how could one determine $$x = B^{-1}(2A + I)(C^{−1} + A)b?$$ I assume the solution has to do with ...