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

learn more… | top users | synonyms

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
159 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
228 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
156 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
357 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
376 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
170 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
168 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
107 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
494 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
23 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
13 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
24 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
68 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
26 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
25 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
19 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
12 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
21 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
14 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
24 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
19 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 ...
0
votes
0answers
27 views

Is $ \| \sum_{i \in [k]} \otimes^3 v_i - T \|_F^2 + \theta \| \sum_{i \in [k]} \otimes^3 v_i \|_F^2$ convex?

I am trying to find the minima of the following equation with respect to $v_i$, $i \in [k]$, to solve an optimization problem but I can't manage to make (stochastic or not stochastic, neither of them) ...
0
votes
0answers
49 views

Prove Norm Theorems

I have the following as given: Let $A \in C^{m\times m}$. Then: 1) $$\lVert A\rVert_1 =\sup_{v\in C^m \setminus\{0\} }{\lVert A_v\rVert_1 \over \lVert v\rVert_1} = \max_{j} \sum_i |a_{ij}|$$ How can ...
0
votes
0answers
16 views

Minimising two interdependent equations with least squares regression.

Originally, I had a set of points in three dimensional space that I was fitting using linear regression. So my model is $$Y = \alpha A+ \beta B$$ where $Y = \{y_i\}$ is the dependent variable, and $...
0
votes
0answers
12 views

matrix optimization problem techniques

I'm looking for some resources on learning techniques commonly used in matrix optimization. For example, minimization of the Frobenius/nuclear/weighted norm of a function of a matrix subject to ...
0
votes
0answers
55 views

Beginner Linear Algebra 1 equation with 3 variables

I do not understand what to put into the remaining values. I tried to solve for the y and z like I did for the x, but the system is telling me that is incorrect. Some help would be appreciated
0
votes
0answers
25 views

Computing a new inverse given information from an earlier inverse:

Suppose I have linearly independent set of vectors $v_1 ... v_k \in \mathbb{R}^{k}$. I can let $B = [v_1 ... v_k]$ and by applying Gaussian elimination on the matrix $$ [ B \ I_k] $$ I end up ...
0
votes
0answers
42 views

Hilbert Matrix, Gaussian Elimination with varying pivot strategies, and computation error.

I'm doing a project for my Numerical Analysis class about computational error related to Gaussian elimination, gaussian elimination with partial pivoting, and gaussian elimination with scaled partial ...
0
votes
0answers
23 views

Matrix approximation

How to solve numerically for non-negative full-rank matrices $P$ and $E$ with the following constraints? $Y$ is a known non-negative matrix with $G$ rows and $N$ columns, $G > N$ 1) $PP^TE^T=PY^...
0
votes
0answers
27 views

Cholesky update of $A'A+\gamma I$

Let $A$ be such that $A'A$ is positive definite and admits the Cholesky factorisation $$ A'A = LL' $$ Let us append a column-vector $c$ in $A$ and define $$\bar{A}=\begin{bmatrix}A & c\end{bmatrix}...
0
votes
0answers
69 views

Sum of squares of eigenvalues

Let $\Lambda(A)$ be the sequence of eigenvalues including repeated eigenvalues, if there exist. Show that $$\inf_{X\mbox{ not singular }} \lVert X^{-1}AX\rVert_F^2=\sum_{\lambda\in \Lambda(A)} |\...