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

learn more… | top users | synonyms

1
vote
1answer
26 views

compare complexity of matrix transpose

Given 2 matrices: $X(rows=m,cols=n)$ and $Y(rows=m,cols=1)$, which of the following operations is computationally easy, i.e., easy on the machine? $$X^{T} \times Y \\ or \\ (Y^{T} \times X)^{T} $$
0
votes
3answers
49 views

Reconstruct a matrix from given eigenvalues

I wanted to know how can I reconstruct a matrix just from its given eigenvalues. I'm really sorry, cause after working on it for 3 days, I haven't any idea about how to do this, therefore I haven't ...
0
votes
1answer
32 views

How do I perform Gram-Schmidt on floating point vectors with epsilons in them?

Let $\epsilon$ be a small positive number such that $1+\epsilon$ and $3+2\epsilon$ are machine numbers but $3+2\epsilon + \epsilon^{2}$ is computed to be $3 + 2\epsilon $. Now, let the (classical) ...
0
votes
0answers
41 views

Way to verify a least-squares solution without actually solving for $x$ and $y$?

I just found the least squares solution of the system $\mathbf{x}A = \mathbf{b} = \begin{pmatrix} x & y \end{pmatrix}\begin{pmatrix} 3 & 2 & 1 \\ 2 & 3 & 2\end{pmatrix} = \begin{...
12
votes
2answers
88 views

How to get the SVD of $2AA^T-\operatorname{diag}(AA^T)$ given $A$ and its SVD $A=USV^T$?

Given a matrix $A\in R^{n\times d}$ with $n>d$, and we can have some fast ways to (approximately) calculate the SVD (Singular Value Decomposition) of $A$, saying $A=USV^T$ and $V\in R^{d\times d}$. ...
0
votes
0answers
45 views

roots of Padé approximating polynomials to the exponential function

I need to obtain (numerically) the roots of the denominator in the Padé approximation to the exponential function $e^{-x}$, in Python. I can calculate its coefficients in closed form (see below). But ...
1
vote
0answers
32 views

Perturbation of a linear homogeneous equation system

Let $A$ be a $n\times(n+1)$ matrix, full row rank. Let $\tilde A=A+\Delta A$ be a perturbation of $A$, again with full row rank. I am interested what is known about bounds on the angle between the ...
2
votes
1answer
51 views

Inverse of a matrix defined by a function

I have a matrix $M$ whose elements are defined by some function $$M_{ij} = f ( |i-j| ) $$ Is it possible to derive a function which defines the elements of the matrix inverse $M^{-1}$ i.e. $$M^{-1}_{...
1
vote
0answers
16 views

Non-linear ODE with diagonal matrix

I have a differential equation of this form: $\frac{dX}{dr}(r)$= M(r)X(r)$ + (\sum_{i}X_i) D(r)X(r)$ $X(r)$ is a size n vector. $M(r)$ and $D(r)$ are n x n matrices with $D(r)$ diagonal. They are ...
0
votes
1answer
22 views

tridiagonal block matrix

Let us consider a linear system of equations $$ Ax=b $$ Where $A$ is a block tri-diagonal matrix, which is given by $$ \begin{eqnarray} A=\left[\begin{array}{ccccc} A_{11} & A_{12} & \dots &...
1
vote
0answers
30 views

Existence of Non-Commutative $4 \times 4$ Matrix Multiplication Algorithm

This paper by a Russian gentleman gives an optimal (?) algorithm for $3$ $\times$ $3$ matrix multiplication. It beats a previously known method by reducing the total number of discrete operations from ...
0
votes
1answer
22 views

Splitting Method

Consider the iteration matrix for the general splitting method $M=I-N^{-1}A$ where $N$ is any invertible matrix. Show that if $\lambda =1$ is an eigenvalue of $M$. then $A$ cannot be invertible. I ...
1
vote
1answer
29 views

Change multiple positions of points on circles with different radius

There are some points which are placed on a circular path: Now I want to change the position of some points equals to the distance value(d) respected to their path. I'm using this formula to ...
2
votes
1answer
81 views

Why is the largest eigenvalue Lipschitz continuous and not differentiable?

Let $$ A:\mathbb R^n\to \mathbb R^{nxn} $$ where $A(x)$ is symmetric for any $x=(x_1,..,x_n)$. $$A(x) = A_0+x_1A_1+x_2A_2+...x_nA_n$$ and all $A$ is positive semidefinite. Consider $$ \underset{x\in\...
0
votes
0answers
33 views

Find a symmetric matrix of minimal Frobenius norm

Let $A\in \mathbb{R}^{n\times n}$ be a symmetric matrix, And let $$x\in \mathbb{R}^n$$ be such that $\lVert Ax-b\rVert_2 = \min_{z\in \mathbb{R}^n} \lVert Az-b\rVert_2$. Show how to calculate a ...
2
votes
1answer
123 views

Prove Operator Norm is a Norm on linear space [duplicate]

Prove that the operator norm defined by $$\left \| A \right \| = \left \| A \right \|_{V\rightarrow W} = \sup_{0\neq v\in V} \frac{\left \| Av \right \|_{W}}{\left \| v \right \|_{V}}$$ (Given norms $\...
0
votes
1answer
41 views

QR Factorization for Inconsistent Linear System

I am trying to recreate the problem found here on finding the least squares solution to an inconsistent linear system via QR factorization. Can someone explain the part about adding on vectors so that ...
0
votes
0answers
28 views

Handling large exponents in a matrix

I have four quantities stemming from a 4th order differential equation. I can represent these as a vector which is a product of a 4X4 matrix $$ M=\left\{v,\frac{\partial v}{\partial x},\frac{\partial ...
0
votes
0answers
19 views

Cutting an Orthonormal Basis

I have constructed an orthonormal basis $\{\mathbf{q_1},\dots,\mathbf{q_n}\}$ for a Krylov set $\mathcal{S}_n(A,\mathbf{x})= \text{span}\{\mathbf{x},A\mathbf{x},\dots,A^{n-1}\mathbf{x}\}$ with $\...
0
votes
0answers
25 views

Relation of the upper triangular factor and the original matrix

Suppose $$PA = LU$$ is the LU factorization(exact) of the square real matrix A, L is the unit lower triangular matrix. Is there a way to determine the relation between the norm of $U$ and the norm ...
0
votes
0answers
28 views

Why does the Lanczos algorithm make an orthonormal basis for the Krylov subspace?

Starting with a $v_0$= $b_0$=0 and a symmetric positive definite matrix A. Why does the following algorithm forms an orthonormal basis span{$v_1$,$v_2$,...,$v_n$} for $K_n$(A,$v_1$)? for k=1,...,n-1 ...
1
vote
1answer
51 views

Damping iterations

Damping is a way of taming a nonconvergent iteration to get it to converge. Given a splitting matrix $M$, which gives the iteration $$x^{k+1} = x^{k} + M^{-1}r^{k}$$ where $$r^{k} = b-Ax^{k}$$ the ...
0
votes
1answer
24 views

equality of the spectrum of two matrices

$Q$ is non singular and A is hermitian. $$V_{+}(A)= Span\{ x: Ax=\lambda x, \lambda > 0 \},$$ $$Q V_{+}(Q^H A Q )= Q Span\{ x: Q^H A Q x=\mu x, \mu > 0 \}.$$ Is it true that $ V_{+}(A)= Q V_{+...
0
votes
1answer
27 views

General form for powers of tridiagonal matrices

Consider a symmetric tridiagonal matrix $A\in \mathbb{R}^{n \times n}$: $$A=\begin{bmatrix} a_1 & b_1 & 0 & \cdots & 0\\ b_1 & a_2 & b_2 && \vdots \\ 0 & \...
0
votes
0answers
61 views

Damped Iteration

For splitting $A = M-P$ a damped iteration with damping factor $\gamma <1$ and scalar $\omega$ is $$x^{k+1} = x^{k} +\gamma M^{-1}r^{k}$$ where $$r^{k} = b-Ax^{k}$$ $$M =\frac{1}{\omega }I $$ $$P = ...
0
votes
0answers
25 views

Preconditioning for Jacobi Method without effect

Show that the following scaling doesn't affect the spectral radius of the Jacobi method iteration matrix $T_{J} = -D^{-1}(L+U)$. $\tilde A=D^{-1 /2}AD^{-1 /2}$, where $D = \operatorname{diag}(a_{11},\...
0
votes
1answer
38 views

Krylov Matrix Tridiagonal Decomposition

I am reading through "Matrix Computations" by Gene H. Golub and Charles F. Van Loan and have come across a proof on the properties of Tridiagonal Decomposition that seems to gloss over parts I do not ...
0
votes
1answer
72 views

Richardson's Methods

I need to prove Richardson's Method and the first part of the proof is: Consider the linear system $Ax = b$ where the eigenvalues of $A$ are real and positive. Let $G_{\omega } = I - \omega A$, ...
1
vote
1answer
40 views

How to test if symmetric matrix is PSD?

Given a matrix that is symmetric, is there a simple way to test if it is PSD? Let us assume that GCT won't work. To me, the simplest (yet probably most naive) test would be solve for the smallest ...
2
votes
0answers
81 views

Inverse of generalized arrow matrix $A = M^T * M + I$

If we have the following linear system: Ax=b And matrix A is created by multiplying a rectangular matrix with it's transpose: $A = M^T * M + I$ What is the best method to solve for x for different b ...
0
votes
1answer
44 views

Proving R is an upper triangular matrix

Let $A\in \mathbb{R}^{n\times n}$ be a symmetric positive definite matrix. Let $x\in \mathbb{R}^n$ with $\|{x}\|_2=1$ and consider the matrix $P=[x,Ax,\dots,A^{n-1}x]\in \mathbb{R}^{n \times n}$. ...
0
votes
0answers
5 views

how to calculate spectrum of a large collumn stochastic matrix

Okay, I have a collumn stochastic matrix of order $280\times 280$, the entries are given in an url in some webpage in row format. I need to find all the eigen values and eigen vector corresponding to ...
1
vote
1answer
64 views

Numerical Methods for finding eigenvalues of large matrices.

I'am writing a small research paper on a problem in linear algebra of my choice. I have chose to do the eigenvalue/vector problem. I know that finding eigenvalues gets pretty much impossible if the ...
1
vote
2answers
46 views

Fast verification of solution to x'Ax<C

Assume we have some complex vector with N dimensions $\vec x$. We need to verify if this is a valid solution to: $\vec x^HA\vec x<C$ where $A$ is a Hermitian matrix and $C$ is some real constant....
0
votes
1answer
13 views

Number of operations required for gaussian elimination of tridiagonal matrix

How do I account for (or rather, not account for) the 0's in the matrix so I don't do more operations than necessary? Thanks.
0
votes
1answer
28 views

Improved error estimate for Conjugate Gradient Method

Let $A \in \mathbb{R}^{n \times n}$ be SPD. The error estimate for the conjugate gradient method is given by \begin{equation} \|x_* - x_m \|_A \leq 2 \left( \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1} \...
0
votes
1answer
55 views

Jacobian of second norm

Find the Jacobian of the following function: (a) $f(x)= \|x -x_0 \|_2$ (b) $f(x)= \log(\|x \|_2)$ Please give me some serious hint!!
1
vote
1answer
33 views

Bounds for the eigenvalues of a matrix in a finite differences scheme

While implementing a numerical solution to a PDE with finite differences, the following scheme arises: $$v_{j+1} = Av_j$$ Where $$A =\begin{bmatrix} 1-4\lambda&(2+\mu h)\lambda&&...
0
votes
0answers
43 views

what's the difference between Eisenstat trick and an implicit preconditioner?

Assume ${A}$ is Hermitian positive definite and $\hat A$=$D^{-1/2}$$A$$D^{-1/2}$ is to obtain a symmetric variant. and $M$=($L_{A}$+$D$)$D^{-1}$($D$+$U_{A}$) where $D$ is a suitable diagonal matrix ...
0
votes
1answer
18 views

Affine transformation does not preserve normal vectors

Consider for simplicity the 2-dimensional space. Define a triangle $T$ on this space that has the vertices $$v_i=(x_i,y_i),\,i=1,2,3$$ Define the reference triangle $\hat T$ as the triangle with ...
0
votes
1answer
28 views

Efficiently find $x(k)$ where $x$ is given by $Ax=b$ and $A$ is tridiagonal

Say $A$ is a $n\times n$ ($n$ odd) real matrix that is tridiagonal (but need not be symmetric). What is the most efficient way to compute the value of $x(\frac{n+1}{2})$ (informally, the 'middle value'...
0
votes
0answers
28 views

Square-root of a matrix which arise from truncating a matrix which has a square-root

I have this covariance matrix $A$ which has a symmetric Toeplitz structure. \begin{equation} A = \left[ \begin{array}{cccccccc} c_0 & c_1 & c_2 & \cdots & c_{n-1} & c_{n} \\ c_1 &...
0
votes
0answers
21 views

Permutation of the posson equation

I have the poisson matrix A, I want to reduce it to the following block matrix: $$ A=\begin{bmatrix} A_{11} & A{12} \\ A_{21} & A_{22} \end{bmatrix} $$, where $A_{11}$ and $A_{22}$ are ...
0
votes
0answers
14 views

Inverse power method - how to decide which $\alpha$ to be used?

Inverse power method - how to decide which $\alpha$ to be used ? I've learnt who inverse power method run, but I don't know how to choose the $\alpha$ $y=(A-\alpha I)^{-1}u_k $ the $\alpha$ here
2
votes
0answers
41 views

skyline storage integration to Cholesky decomposition

I'm trying to develop direct solver for FEM application, solver uses Cholesky decomposition(with following code) but without skyline storage technique, so my question is 2 fold: 1)Comprising skyline ...
0
votes
1answer
17 views

lower bound for the condition number

I have shown that if we have an invertible matrix $A \in \mathcal{M}_{N}(\mathbb{R})$ and $C \in \mathcal{M}_{N}(\mathbb{R})$ such that $A+C$ is singular then $cond(A) \geq \frac{\mid \mid A \mid \...
1
vote
0answers
18 views

for a hermitian matrix, how can I compute the condition number for finding an eigenvalue?

Let $A$ be $m \times m$ hermitian matrix. Let $x$ be a right eigenvector of $A$ with associated eigenvalue $\lambda$. How can I show that the condition number $\kappa $ of computing an eigenvalue is $...
0
votes
0answers
18 views

Prove $\left \| f-L_{k}^{s}f \right \|_{2} = min_{q \epsilon V_{k} }\left \| f-q \right \|_{2} $

Let q be arbitrary and consider the quadratic function of t defined by: $\phi (t)=\left \| f-L_{n}^{s}f+tq \right \|_{2}^{2}$ Note: $L_{k}^{s}f = \sum_{i=1}^{k}(f,p^{i})p^{i}$ for $i = 1,...,k$ ...
0
votes
0answers
28 views

How to compute the Jacobi matrix (tridiagonal matrix) of a polynomial with a recurrence relationship?

I am looking at Trefethen & Bau Exercise 37.1: I have two normalizations of the Legendre polynomials with corresponding recurrence relations: (1) $P_n(1)=1$ which follows $P_n(x) = \frac{2n-1}{n} ...
2
votes
0answers
30 views

Fast computation of component-wise $\exp(-XY^T)G$ for random $G$

I have the following question: Suppose I have two matrices $X,Y$ both of size $m\times p$ and a random i.i.d Gaussian matrix $G$ of size $m \times k$, $m\gg p>k$. Is there a fast way to compute $\...