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

learn more… | top users | synonyms

1
vote
0answers
64 views

Numerical algorithm to solve quadratic eigenvalue problem.

Given the equation $$-4 \left(a^2+a (n-1) (2 t^2-1)\right) \left(\sum _{i=0}^n \alpha_i t^{2 i}\right)^2 \\ +\frac12 \left(\sum _{i=0}^n \alpha_i t^{2 i}\right) \left(t \left(8 a (t^2-1)+1\right) \sum ...
1
vote
0answers
69 views

Kalman Filter Predict Update of LDL Decomposition of a Covariance Matrix

From the state predict equation: http://en.wikipedia.org/wiki/Kalman_filter# $$P_{n+1}=AP_nA^T + Q$$ Suppose the $LDL^{T}$ ( http://en.wikipedia.org/wiki/Cholesky_decomposition#LDL_decomposition_2 ) ...
1
vote
0answers
25 views

Algorithm for finding only the $k$-th singular vectors

I know that we have truncated SVD that can compute the first say $k$ largest singular values (and corresponding singular vectors). However, I'd like to know if there is an algorithm that can find only ...
1
vote
0answers
37 views

Solving a linear equation with a moderatly sparse 1000000*1000000 symmetric matrix

I've got a linear equation $A_{n*n}\cdot x=1_n$, where $n=1000000$ and $A$ is symmetric with approx $1000$ nonzero entries in each column and row. What would be the best numerically stable algorithm ...
1
vote
0answers
28 views

Simultaneous iteration of Symmetric Matrices

Given a Matrix $A$ we can use Simultaneous iteration(Using power iteration on all columns simultaneously) to compute the d biggest eigenvalues. Now this method will give you the biggest eigenvalues, ...
1
vote
0answers
39 views

Gerschgorin Theorem singularity proof

I know how to prove the Gerschgorin Theorem but how exactly would one show that there are no values of $\mu$ s.t. $\mu<0$ for which $A-\mu B$ is singular where $$ A= \begin{bmatrix} ...
1
vote
0answers
28 views

Gaussian Elimination theoretical question

You know how Gaussian Elimination can be broken up into a sequence of L-U premultiplications right? Suppose that there is a matrix $A=a_{i,j} : j=1,...,n$ is an $n × n$ real matrix such that ...
1
vote
0answers
86 views

Least squares of symmetric positive semidefinite matrices

What's the best (in terms of computation time and numerical robustness) way to find the least squares solution of $$Ax = b$$ if $A$ is symmetric and positive semi-definite? If $A$ were symmetric and ...
1
vote
0answers
14 views

Finding eigenvalues in a region

I have an eigenvalue problem (of a very large (n~1000000) but sparse complex system) wherein I need to determine all the eigenvalues in a certain region(a rectangle) in the positive half plane. I am ...
1
vote
0answers
46 views

Representation of Uncertainty in linear systems

I have a linear uncertain system represented by a family of models: $\dot{x}=A_ix$,$i=1,\cdots,N$ I want to represent the system as: $A_i=A_0+B\Delta_iC$ subject to the condition that $\lVert ...
1
vote
0answers
87 views

Algorithm to determine matrix equivalence

I'm a physicist who's not particularly good at linear algebra so please accept my apologies if this is standard textbook stuff that I'm just unaware of. I have two real rectangular matrices $A_{mxn} ...
1
vote
0answers
85 views

is it possible to generate a unique number given a set of N integers regardless of their permutation?

I need to efficiently compute an "id" for a set of N integers, the id needs to be unique if any of the numbers is different from some other set. At the same time the id needs to be the same if the ...
1
vote
0answers
54 views

How can solve this differential equation (third equation )?

How can I solve this differential equation? $$ \frac{dy}{dx}=\sqrt{\frac{A}{y}+\frac{B}{y^2}+\frac{C}{y^4}+\frac{D}{y^5}+\frac{1}{(\frac{1}{y}+\frac{3}{y^2})^2}} $$ where $A,B,C,D$ are constants.
1
vote
0answers
142 views

Proof-finding: Power iteration and complexity of the Rayleigh quotient

I'm searching for a proof for this theorem: \begin{align} |\lambda^{(k)}-\lambda_1| = \mathcal{O}\Big(\Big|\frac{\lambda_2}{\lambda_1}\Big|^{2k}\Big) \end{align} where \begin{align} \lambda^{(k)} ...
1
vote
0answers
68 views

Solving for A in the system Ax = 0

Consider the system of linear equations $A x = 0$ where $A$ is a $K \times M$ matrix of reals and $x$ is an $M \times 1$ vector of reals. The matrix $A$ is unknown but we can generate $x$s that ...
1
vote
0answers
30 views

The least-squares solution for interval data

I would like to solve the least-squares for $\mathbf{Ax} = \mathbf{y}$ with some values in $\mathbf{A}$ and also in $\mathbf{y}$ are interval-valued numbers. In a more detail, e.g.,: $$ ...
1
vote
0answers
208 views

Solving linear system of equations using Successive Over-Relaxation

I was solving a system of linear equations with SOR. I used different values of relaxation factor (w) for the different runs. I found that for all w > w' (1 < w' < 2), the error is the result ...
1
vote
0answers
178 views

Orthogonal Procrustes Problem

The classical orthogonal Procrustes problem concerns finding the matrix $\Omega$ which minimizes $||A\Omega-B||_{F}$ subject to $\Omega'\Omega=I$, with A and B known matrices. Let A be the identity. I ...
1
vote
0answers
80 views

$F(x)=Ax+b$ is a contraction mapping

I want to proof that $f(x)=Ax+b$ with \begin{align} A = \begin{bmatrix} 0 & -\frac{1}{8} & \frac{1}{4} \\ 0 & \frac{1}{3} & 0 \\ -\frac{1}{2} & -\frac{5}{22} & \frac{3}{4} ...
1
vote
0answers
102 views

Applications of Numerical methods

I'm in a course of Numerical Methods and part of an assignment is find an article about an application of numerical methods, explain this article and present a program (in matlab/octave) that ...
1
vote
0answers
87 views

How to condense a matrix to a vector

I'm not an experienced person in mathematics and this might either sound like a trivial question or a stupid one. However, this problem arose to me when I was writing a program. Following is my ...
1
vote
0answers
74 views

Reformulating objective function of canonical correlation analysis

Given two column vectors $X = (x_1, \dots, x_n)'$ and $Y = (y_1, \dots, y_m)'$ of random variables with finite second moments, canonical-correlation analysis seeks vectors $a$ and $b$ such that the ...
1
vote
0answers
43 views

Matrix computing

Given an $n$-vector $x$, show that floating-point computation of the Householder vector $v$ such that $P x = (I − 2vv^{T} )x = \pm\left\|x\right\|_{2}e_{1} $ gives a forward stable result $v^{\prime}$ ...
1
vote
0answers
127 views

Matrix-valued expansion in spherical harmonics

I am seeking a clever solution to the following problem. Given $$X(\theta,\phi) = exp(-iA(\theta,\phi))\; B\; exp(+iA(\theta,\phi))$$ with the square, Hermitian matrix $A$: $$A(\theta,\phi) = A_{0,0} ...
1
vote
0answers
1k 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
105 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
791 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
104 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
204 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
24 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
185 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
127 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
245 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
39 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
394 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
53 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
246 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
290 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
452 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
44 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
136 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
217 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
138 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
190 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
54 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
287 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
89 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?