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

learn more… | top users | synonyms

1
vote
0answers
25 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
49 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. ...
1
vote
0answers
15 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
17 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
27 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
19 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
23 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
39 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 $$ ...
0
votes
0answers
32 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
43 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
0answers
10 views

Could someone explain the difference between the ritz value and harmonic ritz value

could anyone clarify the difference between the ritz value and harmonic ritz value? Is the minimal eigenvalue the harmonic one ?
0
votes
1answer
33 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
27 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
23 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
24 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
43 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
19 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 ...
0
votes
1answer
25 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
53 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
21 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 = ...
0
votes
0answers
17 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
51 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
31 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
74 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
38 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
4 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
0answers
27 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
44 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 ...
0
votes
1answer
11 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
24 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
21 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
29 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 ...
0
votes
0answers
31 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
13 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
27 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 ...
0
votes
0answers
26 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
20 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
13 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
26 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
16 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
13 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
16 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
26 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 ...
0
votes
1answer
38 views

LU Factorization of a full rank square matrix.

If A is an invertible matrix then a necessary and sufficient condition for the LU Factorization to exist is : If A is invertible, then it admits an LU (or LDU) factorization if and only if all its ...
0
votes
0answers
26 views

SVM optimisation problem, finding w

I am finding it difficult to find the value for vector w (weight) for the optimization problem which is: $\min \{ (1/2) * w^T * w : y(i) * w^T * x(i) > 0, \ i = 1,\dots,m\}.$ Can someone ...
0
votes
2answers
36 views

Simplifying the function

Identify for which values of $x$ there is subtraction of nearly equal numbers, and find an alternate form that avoids the problem: $$E = \frac{1}{1+x} - \frac{1}{1-x} = -\frac{2x}{1-x^2} = ...
0
votes
0answers
13 views

Let a and $a_1,…,a_m$ be given vectors i n $\mathbb R^n$ .

Show that two statement are equivalent. (a) For all x ≥ 0 , we have $a'x≤ max a'_i􀂂x.$ (b) There exist nonnegative coefficients $b_i$ that sum to 1 and such that $a \le \sum_{i=1}^m b_i a_i $ can ...
5
votes
0answers
45 views

Maximizing the pairwise Frobenuis distance between M othrogonal matrices

I want to maximize the pairwise Frobenius distance between $M$ orthogonal matrices. That is, I'm looking for $Q_{i}, i = 1, 2, ... M$ such that \begin{equation*} \begin{aligned} & \underset{ 1 ...