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

learn more… | top users | synonyms

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 = ...
0
votes
1answer
37 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
70 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
39 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
62 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 ...
0
votes
1answer
12 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
48 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 ...
0
votes
0answers
41 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
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
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
40 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
17 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
29 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
61 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
27 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
51 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 ...
0
votes
1answer
27 views

Derive formula for condition (A)

Consider the linear system $Ax=b$ where $$ A = \begin{bmatrix}2&4\\1&2+\varepsilon\end{bmatrix} $$ 1) Derive a formula for $\operatorname{cond}_1 ( A )$, the $1$-norm condition number of ...
1
vote
1answer
21 views

How do I find a Solution Common to Many Linear Systems?

So I have the following equation: $$ \sum_{n=1}^{N} S_n f_n(x,y,z) = g(x,y,z) $$ And then for every particular set $\xi$ of $N$ random $(x,y,z)$ points, $\forall x,y,z \in {\mathbb R} $, I can ...
1
vote
1answer
30 views

Calculating $k$ algebraically smallest eigenvalues of a real symmetric matrix

I have a very big matrix assume $1000 \times 1000$. I want to find $k$ of its algebraically smallest eigenvalues where $k$ is $2$ or $3$. I am using MATLAB to solve this problem. My Try: I try to ...
1
vote
1answer
32 views

Proof for error analysis

I am trying to proof the following equality for matrix error analysis. Sorry for all the syntax. I am new to math stack. Thanks in advance. $$b = Ax$$ $r = A(x-\hat{x})$, where $\hat{x} =$ ...
0
votes
1answer
36 views

Elimination problem with polynomial equations involving multiple variables

Hi guys I am very stuck with this problem. I am trying to eliminate 2 out of the three variables it does not matter which one remains, I personally tried keep x and eliminate the others. My question ...
1
vote
0answers
18 views

Solving a system of PDE by fixed point Gauss-seidel iteration method

I have the following system of PDE $$ u-u_0=\operatorname{div}\left(\frac{\nabla u-w}{|\nabla u-w|}\right) \tag 1 $$ $$ \frac{w-\nabla u}{|w-\nabla u|} = \operatorname{div}\left(\frac{\nabla ...
-1
votes
1answer
55 views

Chebyshev interpolation vs equally spaced interpolation [closed]

Which one is better to use and why? What's the advantage of Chebyshev interpolation over equally spaced interpolation and vice versa?
0
votes
1answer
83 views

Rayleigh quotients being the diagonal entry of a matrix after orthogonal transformation

So there's this problem in Numerical linear algebra by Trefethan and Bau a textbook I am reading. (It's great! basically taught me MATLAB and some great numerical methods, its also free!) The ...
1
vote
1answer
30 views

Separable linear programs

Assume, we have two distinct LPs: \begin{equation*} \begin{aligned} & \text{min}_{x_1} & & c_1^Tx_1 \\ & \text{subject to} & & A_1x_1 = b \\ & & & x_1 \geq 0 \\ ...
0
votes
1answer
33 views

Under-determined linear system, showing any solution can be written as $x_{0} + Zw$

In my notes for under-determined linear systems, the following is just given as fact, but I've restructured it as a question because I don't quite understand it. Consider $Ax=b$ where $A$ is an ...
1
vote
0answers
50 views

Given a CRS stored matrix A, provide an algorithm for calculating vector u.

Given an $NxN$ matrix $A$ and vectors $u,v,b$ such that: $$u_i = {\frac1{a_{ii}}}(b_i - \sum_{j=1,j\neq{i}}^n a_{ij}v_i)$$ And considering $A$ is stored using CRS, provide an algorithm (or ...
0
votes
0answers
21 views

number of iterations for the generalized conjugate residuals method?

I have the matrix $n \times n $ defined as: $A=\begin{bmatrix} 0 & 1 & 0 & \dots& 0 \\ 0 & 0 & 1 & \dots &0 \\ \dots &\dots ...
0
votes
0answers
23 views

Generalized conjugate residuals method applied to a block matrix

I have the diagonal block matrix A with $2 \times 2$ k-blocks given by : $D_k=\begin{bmatrix} 1 & k\\ 0 & 1 \end{bmatrix} $. I have to show that the generalized ...
0
votes
1answer
38 views

How many divisions needed for LU Decomposition of a square matrix

If a general matrix is of dimensions $n \times n$, how many divisions are needed to compute the LU Decomposition of this matrix? Can we say zero divisions are needed (it can be done with only ...
0
votes
1answer
87 views

Hyperplane Matrix Linear transformation

Let $$u =\begin{bmatrix}u_1\\.\\.\\.\\u_n\end{bmatrix}$$ be a nonzero vector in $\mathbb R^n$, and let $T:\mathbb R^n \to \mathbb R^n$ be the linear transformation given by $T(x) = u^\top x$. ...
0
votes
2answers
42 views

Relation between perturbed matrix and condition number of the matrix

If A is non‐singular but the perturbed matrix (A+δA) is singular, then show that  $$∥A∥/∥δA∥≤y $$ Where y is condition number of the matrix A. Tried for a solution The relation $$(A+δA)(x+δx)=b $$ ...
0
votes
1answer
27 views

Power Method: Showing convergence to dominant eigenvector

What follows is taken from Numerical Analysis, by R. Burden and D. Faires: Let $A\in \mathbb{R}^{n\times n}$, with eigenvalues $\lambda_1,\dots,\lambda_n$ such that $|\lambda_1|>|\lambda_2|\ge ...
0
votes
0answers
21 views

Conjugate gradient method and rietz values

I'm working on the conjugate gradient method. I have the matrix A, defined as A= diag(v) where $v=[ones(1,10), 11:1000]$. I have to solve the system $Ax=b$ ,b=ones(1000,1) with the conjugate ...
1
vote
1answer
53 views

What is the largest floating point number a so that fl(100 + a) = 100?

What is the largest floating point number a so that fl(100 + a) = 100? Here is how float number is computed. $fl(a ⊙ b) = (a ⊙ b)(1 + δ)$. Where $|δ| ≤ ε$. Furthermore, $ε = 2^{-53}$. My ...
2
votes
0answers
26 views

Looking for matrices such that $\kappa(A) =1$

Looking clues for this problem. Find all the matrices such that $\kappa(A) = 1$ We define $\kappa(A) = \|A\|\,\|A^{-1}\|$. If I'm looking matrices such that $\kappa(A) = 1$, I was thinking in ...