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

learn more… | top users | synonyms

4
votes
1answer
128 views

QR decomposition help

What do Q and R stand for? Why must the diagonal entries of R be positive instead of just nonzero?
3
votes
1answer
102 views

An Extension to the Generalized Eigenvalue Problem

Given two square matrices $A,B \in \mathbb{R}^{n\times n}$, the generalized eigenvalue problem is finding the scalar $\lambda \in \mathbb{C}$ and vector $x \in \mathbb{C}^{n}$ such that $$ A ...
3
votes
1answer
66 views

Relationship between the solution to $Ax=b$ and $(A+I)x=b$

I have have a symmetric, tridiagonal, Toeplitz matrix $A$, where $A_{11} = -\frac{1}{2}$ and $A_{21} = 1$, and I need to solve the system $$ (A+I)x=b, $$ numerically where $b$ does not necessarily ...
3
votes
1answer
77 views

Necessary and Sufficient conditions for convergence of matrix iterations

I need some help figuring out how to go about the iteration part of the problem...I don't really know where to start. If someone can please help take me through it that would be greatly appreciated. ...
3
votes
1answer
150 views

A Beautiful Determinant!

Find the determinant of the following matrix in the terms of $a_1,a_2,\cdots,a_n$ explicitly, $$ \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_n\\ a_2 & a_3 & a_4 & \cdots ...
3
votes
1answer
132 views

How to solve this system of 3 equations with 3 variables?

I stumbled upon this system with constants $a_{i,j}>0$ that I want to solve for $x,y,z \in\mathbb{R}$: \begin{align} a_{2,1}y+a_{3,1}z=& x(y+z) \\ a_{1,2}x+a_{3,2}z=& y(x+z) \\ ...
3
votes
1answer
91 views

Understanding higher order SVD

Can someone explain the singular value decomposition of a tensor (maybe a 3 dimensional matrix) with an example? It is intuitively difficult to the get the meaning from just the formulas. On a ...
3
votes
1answer
198 views

Computational cost, power method and page rank

When solving the PageRank problem for $n$ web pages, it is necessary to find a solution of the eigenvector equation $$(fM)*p = p,$$ where $$fM = dM + (1 - d)Z$$ $$Z =\frac{1}{n}*ee^T$$ $$e =[1, 1, ...
3
votes
1answer
243 views

How to Store a Banded Matrix by Diagonal

I'm taking a graduate level independent study course this semester in Matrix Computations. I'm not getting much support from the professor, so am turning to the excellent StackExchange community for ...
2
votes
1answer
27 views

How to prove Kahan's example on componentwise pertubation theory?

In Matrix Computations (4th edition) by Gene H. Golub and Charles F. Van Loan, Problem 3.5.3 asks the following problem (and citing Kahan, William. "Numerical linear algebra." Canadian Math. Bulletin ...
2
votes
1answer
57 views

Eigenvectors of transition matrices in PageRank algorithm

In my probability course, we were discussing applications of Markov Chains to computer science -- in particular, how the PageRank algorithm goes about finding stationary distributions, and thus, ranks ...
2
votes
1answer
99 views

Least squares problem with orthonormality constraints

Given $y_1,\ldots,y_n\in \mathbb{R}$,$w\in \mathbb{R}^d$, and $x_1,\ldots x_n\in \mathbb{R}^D$, how do we solve the following optimization problem \begin{align} \min_A \sum_{i=1}^n (y_i-w^TA^Tx_i)^2\\ ...
2
votes
1answer
84 views

fast multiplication for a matrix and its transpose.

I know Strassen and other methods can achieve better than $O(n^3)$ for general square matrix multiplication. I am curious of the spacial case where the multiplication is between a $n*m$ matrix $A$ ...
2
votes
1answer
135 views

SOR and Gauss-Seidel Method - Confusion

Can anyone explain to me the SOR Method for finding the root(s) of a function? Its supposedly very similar to the Gauss-Seidel method. The Gauss-Seidel method, from my understanding, is similar to ...
2
votes
1answer
229 views

1D Schrodinger/Laplace equation via finite differences: incompatible eigenvalues

I need to solve a variant of the 1D Schrodinger's equation equation using finite differences, so I decided to play a little bit with the real-space representation of some operators. Using the ...
2
votes
1answer
80 views

Numerical methods for inverting non positive definite matrices

I'm working on a PDE solver and need to invert the following matrix written in block form $\left( \begin{array}{cc} kM & -S \\ -S & M \end{array}\right) $ where M and S are the usual mass and ...
2
votes
1answer
167 views

Question on “avoidance of crossing”

In review of linear algebra I come across this phenomenon, the Google Book link is this: What I do not understand is Lax tried to persuade us that "there is another way of parametrizing these ...
1
vote
1answer
20 views

Error bound of midpoint rules with unbounded second derivative

It is well known that error bound of midpoint rule for function $f[a,b]$ is given by $$ E\leq K\frac{(b-a)^3}{24 n^2} $$ where $|f(x)''\leq K|$ and $n$ is the number of time steps. if second ...
1
vote
1answer
29 views

What happens if the power method is applied with a starting vector $q=c_2 v_2+…+c_n v_n$ in the presence of roundoff errors?

Supose $\{v_1,...,v_n\}$ is an eigenvector basis and $|\lambda_1|>|\lambda_2|>\ldots >|\lambda_n|>0$, so, my question is, if our starting vector $q \in span\{v_2,\ldots,v_n\}$ and in the ...
1
vote
1answer
22 views

Polar decomposition varient

I have a factorisation to do, and I think that a varient of Polar decomposition will give me what I need, although I'm not sure of the exact form. I have \begin{equation*} \mathbf{y} = ...
1
vote
1answer
73 views

Properties shared by similar and unitary similar matrices.

We know that matrices $A$ and $B$ are similar if there exists an invertible matrix $P$ such that $A=PBP^{-1}$ and they are unitarily similar if $P$ is unitary ($PP^*=P^*P=I$). I want to know : What ...
1
vote
1answer
57 views

How page rank relates to the power iteration method

I do not see how pageRank relates to the power method. Since for the pageRank we are looking for the steady stable state (vector) for a Markov (transition) matrix and the matrix has already an ...
1
vote
1answer
49 views

showing condition number of a matrix is the square root of $A^\top A$

For $A \in \mathbb{R}^{m\times n} : m > n, A$ has full rank, I want to show that $k(A^\top A) = k(A)^2$, is there a way to do so purely from $k(A)=norm(A) norm(A^\dagger)$? Recall that $A^\dagger ...
1
vote
1answer
18 views

Coordinate transformation (or conversion) into yards

Following is a soccer field with its dimensions. There is a similar field, but I am capturing coordinates via mouse-movement. So, what (115,75) shows here, is ...
1
vote
1answer
56 views

How to find Housholder reflection

For example, let say I have a matrix$$ \left(\begin{array}{rrr} 3 & 3 & 0 \\ 0 & 0 & 0 \\ 4 & 1 & 3 \end{array}\right) $$ and the Householder has the form $H = I -2uu^T$, and ...
1
vote
1answer
27 views

Trying to show convergence of a Forward Euler method based on step size restriction

I have shown that for the given ODE system, that when we apply the forward Euler method to something like \begin{align} \mathbf{y'} &= A\mathbf{y} \\ \mathbf{y}(t_{0}) &= y_{0} \\ t &\in ...
1
vote
1answer
77 views

How to obtain a convergent solution iteratively for a linear system of equations?

I am working on a problem that requires an iterative procedure to solve a linear system of equations, the system of equations in matrix form is: $$\underbrace{\begin{bmatrix} r_{11} & r_{12} ...
1
vote
1answer
32 views

Perspective transformation matrix application

I need to transform an angled photographed pice of paper to a "flat" image. I found this question & solution here on Mathematics and tried it out for the image given in the solution: The values ...
1
vote
1answer
41 views

Recover the inverse after interative solution of a linear system

I have solved the linear system $\mathbf{A} \mathbf{x} = \mathbf{b}$ with an iterative solver. The problem is well-posed ($\mathbf{A}$ is invertible, $\mathbf{b} \ne \mathbf{0}$, blah blah blah). ...
1
vote
1answer
35 views

Is LU decomposition of matrices efficient for today's standards?

This is in the spirit of a previous question of mine about the efficiency of the QR algorithm. The reason for asking is that I want to motivate some students, and I'm also curious. I do understand ...
1
vote
1answer
37 views

A problem about lub and glb of matrix

For any matrix $A\in \mathbb{C}^{n\times n}$, define $$lub_K(A):= \inf\{\alpha\geq 0: AK\subset \alpha K\},$$ and $$glb_K(A):= \sup\{\alpha\geq 0: \alpha K\subset AK\},$$ where $K$ is a equilibrated ...
0
votes
0answers
48 views

System of linrar equations and condition number

The relative error of the solution of a system of linear equation $Ax=b$, for any natural norm $\|\cdot\|$ is bounded by $$ \frac{1}{\| A\| \|A^{-1} \|} \frac{\|r\|}{\|b\|} \le \frac{\|e\|}{\|x\|} \le ...
0
votes
0answers
44 views

What is the largest (dense, real, symmetric) random matrix I can diagonalize on a computer?

I have read that 10.000x10.000 is no problem for LAPACK or similar routines. I would like to know if N=20.000 or 40.000 is possible. EDIT: I don't know if it is relevant, but the matrix is positive ...
0
votes
0answers
60 views

Strange Convergence of SOR/Gauss-Seidel

I am having trouble with the convergence of my Gauss-Seidel/SOR method. The matrix $A$ in $Ax=y$ seems to be positive-(semi)definite. Its eigenvalues are: However, the method (SOR) improves the cost ...
0
votes
0answers
74 views

How to find a transformation matrix T?

(1.) Suppose there is matrix C of dimension "p by n" where p is less then n i.e. p I want to know is there any particular way exist to find transformation matrix T of dimension "n by n" such that ...
0
votes
0answers
28 views

Not enough memory for GMRES

After realizing that Gauss-Seidel is extremely slow for my simulation, i wanted to try GMRES and luckily found the C++ code here without diving into the theory. The size of the matrix in my case is ...
0
votes
0answers
100 views

Francis Algorithm (Implicit QR Algorithm)

In Numerical Analysis, we are touching upon QR and Francis Algorithm. I understand that for Francis's Algorithm, we reduce the matrix to its upper Hessenberg form using Householder transform. What I ...
0
votes
0answers
78 views

Upper Hessenberg Form

I am given a matrix. I would like to reduce it to its upper Hessenberg Form. We are discussing eigenvalue computations in Numerical Analysis and the textbook just gives the algorithm for it without an ...
0
votes
0answers
56 views

QR Algorithm with Shifts Question

Why must QR Algorithm with Shifts make no progress when applied to this n x n matrix? (attached as image). Also, if a matrix A is orthogonal in a QR factorization, will R be tridiagonal? How would ...
0
votes
0answers
72 views

convergence for symmetric, positive semi-definite operator

Assume $u$ is a vector in the Euclidean space $\mathbb{R}^N$, $||u||=\sqrt{\langle u, u\rangle}$, where $\langle u, v\rangle = \sum_{i=1}^N u_i v_i$. I have that $||u^{k+1}-u||\leq ||I - c ...
0
votes
0answers
22 views

Is any method which allows segmentation of long diagonalizing procedures?

This is a question for a smarter way of numerical computation. When I diagonalize a certain type of Vandermonde-matrices in Pari/GP ("mateigen(M)"), for instance of size 16x16 then this can be ...
0
votes
0answers
30 views

only calculate diagonal of cholesky decomposition

I have a massive matrix $A$ that I can't hold entirely in memory, but it is possible to easily calculate individual entries ($A(i,j)$). I'm only interested in calculating the diagonal entries of the ...
0
votes
0answers
207 views

when fixed Point Iteration does not converge?

I want to solve a nonlinear system with the fixed point iteration method. I have initial condition,and the answer is known. By using this method the answer converges very slowly about 1000 iteration ...
0
votes
0answers
69 views

How to solve a divergent linear system using iterative methods?

I have a matrix A which is symmetric and non-diagonal dominant. I tried to use Jacobi/Gauss-Seidel/SOR to solve it but it diverges. Is there any mechanism to condition the matrix for convergence ...
0
votes
0answers
212 views

Symmetric Tridiagonal QR Algorithm

I have a question regarding QR algorithm. Suppose we are being given a symmetric tridiagonal matrix A (4X4) and perform QR factorization on A: A=QR. Then we define A':=RQ. A' still possesses the ...
0
votes
0answers
62 views

Minimizing an expression with linear constraints

Given a system of under-constrained (i.e. infinite solutions) linear equations (all values will be integers, all coefficients will be 0, 1, or -1), I want to pick values for the variables to minimize ...
0
votes
0answers
50 views

Is there any risk to transform to $(B^{T} \otimes A)\operatorname{vec}(X)=\operatorname{vec}(C) $ for solving $AXB=C$ for X

To solve the equation $AXB=C$ for X, we can use the property of vec operator and kronecker product to transform to $(B^{T}\otimes A)\operatorname{vec}(X)=\operatorname{vec}(C)$, where ...
0
votes
0answers
118 views

Can antiunitary symmetry be used to calculate determinant of a matrix

Suppose I have some $N \times N$ complex matrix $A$, that commutes with some antiunitary operator $U$ that satisfies $U^2 =-1$. It can be shown that $\det(A)\ge 0$ , because for every eigenvector ...
0
votes
0answers
167 views

Divide and conquer possible on linear equation systems?

Suppose a 4-connected regular grid $$\mathcal{G}=(\mathcal{E},\mathcal{V}),$$ where $\mathcal{E}$ and $\mathcal{V}$ denote the set of edges and vertices of that grid, respectively. Given this ...
0
votes
0answers
352 views

Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $F(x)$ $F(x) = \sum_{i=1}^{M}||x_{i+1} - x_i - K(\frac{x_{i+1} + x_i}{2})||^2 + ||x_1-c_1||^2 + ||x_N-c_2||^2$ , where $x$ is a vector of $N$ scalars, $c$ are ...