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

learn more… | top users | synonyms

1
vote
0answers
18 views

Check feasibility of a system of integer linear equations

I'm currently working on a very large integer linear programme which cannot be solved within any reasonable time. The initial set of linear equations S={Ax<=b) is feasible. I want to add more ...
1
vote
0answers
28 views

Influence of preconditioning on degenerate eigenvectors

I'm using a hierarchical decomposition of a sparse matrix $A$ as suggested here. I find that the method essentially finds eigenvectors using the QR algorithm. $A$ has some eigenvalues with ...
1
vote
0answers
58 views

Newton's method for multidimensional functions

Can Newton's method be used to find the root of a function f : $\mathbb{R}^n\to\mathbb{R}^m$. Can anyone provide a proof for this? (I have checked the method of solving system of equations with ...
1
vote
0answers
19 views

Change in Singular Value Decomposition of a matrix on addition of a single row

Given that I know the svd decomposition of a matrix, is there any way to compute the svd decomposition of the matrix obtained by adding a single row to the original matrix? Is there any relation ...
1
vote
0answers
21 views

If symmetric matrix in a least-square deconvolution problem positive definite?

I want to apply Gauss-Seidel method in a least square deconvolution problem. The convolution of two vectors is written in: $h * x = z$. $$z(n) = \sum_{i=0}^{N-1}h(i)x(n-i)$$ It is a linear transform ...
1
vote
0answers
43 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
19 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
38 views

Best way to solve specific block-tridiagonal linear system (10000x10000 and larger)

To provide more context, this system came from energy balance equation on a mesh with (n,m) nodes in each direction. It's a linear system that looks like this (size of system in blocks n = 4, size of ...
1
vote
0answers
28 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
22 views

Vector optimization with set constraint

This is a more generalized form of a previous unanswered question, from which I've removed all the content that wasn't relevant to the actual problem. I have a minimization problem of the form $$ ...
1
vote
0answers
25 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
31 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
22 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
37 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
74 views

Inverse of the sum of a symmetric and diagonal matrices

I have two square matrices, $A$ and $B$. $A$ is a block symmetric matrix with 1's along the diagonal (and therefore 1's in whole blocks along the diagonal). $B$ is a block diagonal, with the same ...
1
vote
0answers
13 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
44 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
62 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
82 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
66 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
59 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
25 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
121 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
80 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
49 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
72 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
56 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
56 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
40 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
107 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
690 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
101 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
462 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
78 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
156 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
324 views

What is the Moore-Penrose pseudoinverse for scaled linear regression?

The matrix equation for linear regression is: $$ \vec{y} = X\vec{\beta}+\vec{\epsilon} $$ The Least Square Error solution of this forms the normal equations: $$ ({\bf{X}}^T \bf{X}) \vec{\beta}= ...
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
133 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
97 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
155 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
35 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
201 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
45 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
150 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
72 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
196 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
20 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
398 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
41 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
109 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 ...