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

learn more… | top users | synonyms

1
vote
0answers
892 views

The spectral radius of the matrix $A$ is less than or equal any natural norm

Show that the spectral radius of the matrix A is less than or equal any natural norm, i.e: $$\rho(A) \leq ||A||=\max_{||x||=1}{||Ax||}$$ where $\rho(A)=\max\{|\lambda|:\lambda \text{ is a eigenvalue ...
1
vote
0answers
103 views

Fast way to find a matrix with only $0$ and $1$ as entries full-rank or not?

I have a huge number of small Zero-One Matrices($4\times 4$, $5\times5$,$6\times6$) and I want to determine whether they are full-rank or not one by one. Gaussian elimination is a option, I want to ...
1
vote
0answers
629 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 ...
1
vote
0answers
87 views

Matrix in Matlab

I'd like to compute the centralizer of a subgroup $H$ of orthogonal group $O(8, R)$, so I need to solve the equation $AX=XA, BX=XB \mbox{ where } H=\langle A, B\rangle.$ The problem that I have is ...
1
vote
0answers
184 views

Matrix spectral decomposition

Let $A$ be a square matrix $(N \times N)$ and $a_{ij} \in \mathbb{R}$. Suppose A has N eigenvalues $\lambda_{1} < \lambda_{2} < ...\lambda_{n} \in \mathbb{R}$. $A$ = $R \Omega R^{-1}$ its ...
1
vote
0answers
23 views

Short-cut to a group of long sums/differences

If I have data $a,b,c,d$, and want to calculate $x=a+b-c-d$, $y=a-b-c+d$ and $z=a+b+c-d$, I can save three adds by doing $e=a-c$, $f=b-d$, then $x=e+f$,$y=e-f$, $z=a+c+f$. If I have 100 data values ...
1
vote
0answers
152 views

How to Diagonalize an Extremely Large Sparse Matrix in SLEPc/PETSc

Dear Friends, Recently I have started with learning SLEPc/PETSc, but I didn't find a way to solve my problem. I have to solve a big sparse matrix which is a two dimensional quantum ...
1
vote
0answers
110 views

Existence criteria for the LU decomposition of a tridiagonal matrix

In this link, the following result is presented without proof: Let $a, b, c$ be the lower off diagonal, diagonal, and upper off diagonal elements of a tridiagonal matrix. A pivotless LU ...
1
vote
0answers
198 views

About the Generalized singular value decomposition (GSVD).

I have studied about Singular value decomposition (SVD) and had solved few numerical examples to understand SVD. Now I am studying Generalized singular value decomposition (GSVD). I followed this ...
1
vote
0answers
37 views

Algorithm to compute similarity computation

I have a similarity transformation of matrices from the type $B = P^{-1}AP$. It is known that $A$ and $P$ are invertible matrices, but not orthogonal. Given that I have the matrices $P$ and $A$ I ...
1
vote
0answers
287 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[ ...
1
vote
0answers
51 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
197 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
92 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 ...
1
vote
0answers
242 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
21 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
424 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
43 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
117 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 ...
1
vote
0answers
210 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
128 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$ ...
1
vote
0answers
175 views

Simultaneous Eigenvalue Problem

I have what I think is a simultaneous eigenvalue problem in three parameters: $$\alpha A_1x + \beta B_1x + \gamma C_1x + D_1x = 0$$ $$\alpha A_2x + \beta B_2x + \gamma C_2x + D_2x = 0$$ $$\alpha A_3x ...
1
vote
0answers
51 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
260 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
88 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
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?
1
vote
0answers
132 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
144 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
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, ...
1
vote
0answers
101 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
396 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
15 views

order of convergence for approximations

Let $u \in L^{2}(0,1)$ and $0 < x_{1}< x_{2}<... < x_{n} = 1$, where x$_{k}$ = k$\cdot$h, n$\cdot$h = 1, a partition of the interval [0,1]. Define I$_{k}$(x) = 1 if x $\in$ [x$_{k}$, ...
0
votes
0answers
12 views

Location and perturbation of eigenvalues

This is a problem from Horn and Johnson's Matrix Analysis. I'm having trouble showing the bolded parts in the following paragraphs. In fact, I don't really understand what the sentences mean. I would ...
0
votes
0answers
23 views

A problem on Gersgorin cirle passing through the eigenvalue of an absolute matrix

I'm having trouble solving the following problem. I think I need to show that the matrix $D^{-1}|A|D$ has property SC, but I can't come up with a way to show it. I would really appreciate any ...
0
votes
0answers
29 views

Is the following matrix Upper Hessenberg?

Does $$ A = \begin{pmatrix} 1 & 1 \\ -1 & -1 \end{pmatrix}$$ properly satisfy the definition of upper Hessenberg?
0
votes
0answers
32 views

Applying Central Difference (Finite Difference Method) in MATLAB

I was given a rather complicated few problems to solve in MATLAB using the central difference method, and I'd like some help figuring out how to translate this into code. The goal is to discretize ...
0
votes
0answers
30 views

Show that Newton’s Method is well-defined for all k and converges to 0 for $x_0>0$

Let $f : R → R$ with $f$ twice continuously differentiable, $\gamma > f''(x)>\delta, f(0)=0,f'(x)>\rho $ for $x ≥ 0$. Show that for any $x_0 > 0$ that Newton’s Method is well-defined for ...
0
votes
0answers
16 views

Jacobi Iteration with Shift

The question is to solve a linear system using Jacobi iterations with a shift of mu = 5. My code converges very quickly, but it does not yield the results that MATLAB gives with the backslash ...
0
votes
0answers
8 views

Convergence of recursive application of finite-difference operator to $C^{\infty}$ functions

Let $f\colon \mathbb{R}\to \mathbb{R}$ be an arbitrary smooth function (whose extension to a complex differentiable function is entire, if it matters). Let $\mathbf{D}_{h}$ be a finite difference ...
0
votes
0answers
6 views

Get stuck with some statements of convergence rate of the iteration method from “Iterative methods for sparse linear systems (2nd edition) ”

Here are the statements I get from the book and the two highlight parts are what I can not understand well. The questions are: Why we can conclude that $\rho=\rho(G)$ from"the above analysis"? ...
0
votes
0answers
20 views

Interpolation question about polinomials?

Let $f(x)=x^n$. show that for each $n$ distinct point $x_0,... x_n$ we have $f[x_0,...x_n]=0$ and $f[x_0,...,x_{n-1}]=\sum_{i=0}^{n-1}x_i$. also show that if $x_{i+1}-x_i$ is fixed for each $i\ge 0$ ...
0
votes
0answers
10 views

Applying perturbed matrix to unperturbed eigenvector

Suppose we've got a matrix $P$ and a perturbed version $\hat{P}=P+E.$ Given that $v$ is an eigenvector of $P$ with $Pv=0,$ I'd like to get as sharp a bound as possible on $\hat{P}v$ (in terms of ...
0
votes
0answers
33 views

Matlab project - Jacobi method for tridiagonal matrices…

I have to do a project in Matlab to my University and I don't quite understand what I should do. I was given script that solves systems of equations with Jacobi's method with given tolerance and ...
0
votes
0answers
16 views

$Tn(x) =\frac{(x-\sqrt{x^2-1})^n+(x+\sqrt{x^2-1})^n}{2}$, show that $|Tn(x)| \le 1,\forall x \in [-1,1]$

$Tn(x) =\frac{(x-\sqrt{x^2-1})^n+(x+\sqrt{x^2-1})^n}{2}$, show that $|Tn(x)| \le 1,\forall x \in [-1,1]$
0
votes
0answers
11 views

Consistently obtaining the negative of the correct eigenvalue in hand calculations

The question is "find the eigenvector of A corresponding to the given eigenvalue" A = | 1 0 2 | |-1 1 1 | | 2 0 1 | Eigenvalue = -1 Add -1 * I to A Row reduced to | 1 0 1 | | 0 1 1 ...
0
votes
0answers
30 views

QR Algorithm without Shifts (Trefethen and Bau)

A real symmetric matrix $A$ has eigenvalue 1 of multiplicity 8, while all the rest of the eigenvalues are $\leq 0.1$ in absolute value. Describe an algorithm for finding an orthonormal basis of the ...
0
votes
0answers
17 views

Strictly diagonally dominant matrix -LU factorization

Let $A\in\mathbb{C^{n\times n}}$ be strictly diagonally dominant. I want to show that the LU factorizations with and without partial pivoting are the same for these matrices. For start, I created ...
0
votes
0answers
12 views

Pairing Two Point Clouds

So I have two point clouds $X$ and $Y$ each with $N$ points in the familiar $\mathbb{R}^3$ euclidian 3D space. I then have an inter-point distance $d(\vec x_i,\vec y_j)$ which is zero if $\vec x_i$ is ...
0
votes
0answers
9 views

Relative Error with Respect to Frobenius Norm

I'm look at this tiny book called "Deblurring Images: Matrices, Spectra, and Filtering" by Hansen, Nagy, O'Leary. This is a self study, but I believe my question is broad enough so that it can be of ...