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

learn more… | top users | synonyms

1
vote
0answers
127 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 ...
0
votes
0answers
48 views

Can I detect repeated eigenvalue by inverse iteration?

Suppose all eigenvalues of $A$ are nonnegative. By using inverse iteration $A-\mu I$ for many values of $\mu\ge 0$, I can find eigenvalues of $A$. If $A$ is a $n\times n$ matrix and have different $n$ ...
2
votes
3answers
135 views

On integral of a function over a simplex

Help w/the following general calculation and references would be appreciated. Let $ABC$ be a triangle in the plane. Then for any linear function of two variables $u$. $$ \int_{\triangle}|\nabla ...
0
votes
0answers
129 views

Shifted inverse power method in Octave.

EDIT: Ok, I've managed it. It was very stupid bug... I must write $p=L\(P*z0)$ etc.... I'm trying to write a function which returning vector $a$ (vector of eigenvalues of matrix $A=A^T \in ...
0
votes
0answers
31 views

Error bound on matrix vector multiplication

I am multiplying a matrix $A$ with vector $p$. However, the matrix $A$ isn't accurate. Some (a very small fraction) of the element's value is changed from $a_{i,j}$ to {0,$-a_{i,j}$, $2a_{i,j}$}. ...
3
votes
0answers
60 views

Solver for sparse linearly-constrained non-linear least-squares

Reposted from stackoverflow on the advice of Nick Rosencrantz: Are there any algorithms or solvers for solving non-linear least-squares problems where the jacobian is known to always be sparse, and ...
1
vote
0answers
33 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 ...
2
votes
1answer
63 views

Block matrix notation

Given that $A$ is a real, rectangular matrix of dimension $m \times n$ and $\begin{align} A = \left[\begin{array}{c} I \\ e^{\intercal} \\ -e^{\intercal}\end{array}\right] \end{align}$ is represented ...
1
vote
2answers
83 views

solving linear recurrence - general solution confusion

I've been trying to get my head around this for days. I understand what is going on with the calculation of a linear recurrence and I also understand how the characteristic is obtained. What is ...
3
votes
1answer
95 views

About iterative refinement to the solution of the linear equations

I want to know what is iterative refinement for improving the solution to the linear equations? How they improve solutions and what are the various techniques for the iterative refinements? Any ...
1
vote
0answers
157 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[ ...
0
votes
1answer
166 views

error for Conjugate gradient method

Suppose A is a real symmetric 805*805 matrix with eigenvalues 1.00, 1.01, 1.02, ... , 8.89,8.99, 9.00 and also 10, 12, 16, 36 . At least how many steps of conjugate gradient iterations must you take ...
4
votes
1answer
541 views

Sum of eigenvalues and singular values

How one can prove that for a matrix $A\in \mathbb{C}^{n\times n}$ with eigenvalues $\lambda_i$ and singular values $\sigma_i$, $i=1,\ldots,n$, the following inequality holds: $$ \sum_{i=1}^n ...
0
votes
1answer
48 views

$\lambda_{min}\left (\frac{A+A^*}{2} \right )\leq \sigma_{min}(A)$

For $A \in \mathbb{C}^{n \times n}$, how to show that $\displaystyle \lambda_{min}\left (\frac{A+A^*}{2} \right )\leq \sigma_{min}(A)$?
2
votes
2answers
398 views

Minimum eigenvalue and singular value of a square matrix

How to show that the relationship $\left | \lambda_{min} \right | \geq \sigma_{min}$ holds between the minimum eigenvalue and singular value of a square matrix $A \in \mathbb{C}^{n \times n}$?
1
vote
0answers
44 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 ...
0
votes
1answer
218 views

Largest and smallest eigenvalues of a hermitian matrix

How to show that the largest and smallest eigenvalues of a hermitian matrix $A \in \mathbb{C}^{n \times n} $ can be found as: $\displaystyle \lambda_{max} = ...
0
votes
1answer
166 views

What is the error in Newton's Method for Matrix Inversion?

I need it to invert a matrix. Wikipedia explains that there is a generalization of the Newton Method for matrices. However, there is nothing mentioned about the error bounds. Suppose we have, as ...
1
vote
1answer
371 views

Underdetermined linear systems least squares

I have an underdetermined linear system, with 3 equations and four unknows. I also know an initial guess for these 4 unknows. The article I am reading says: We can solve the system using the least ...
0
votes
1answer
443 views

Condition number for non-square matrix?

From what I understand the condition number of a non-square matrix A is its largest singular value divided by its smallest nonzero singular value: $\kappa(A) = \sigma_1/\sigma_n $. Where ...
2
votes
1answer
47 views

Problems where SPD linear system arises

I know some of the places where SPD linar systems arises such as elliptic PDEs and normal equations. Can I have a more comprehensive list of scientific applications which require solving SPD linear ...
3
votes
1answer
237 views

Polynomial Condition Number

I have a question, from "Applied Numerical Linear Algebra"(James W. Demmel), that I don't know how to do. Consider $\mathbb{R^{d+1}}$ as the set of polynomials of degree $\leq d$ and $S_a$ the set of ...
4
votes
2answers
308 views

Matrix Calculus in Least-Square method

In the proof of matrix solution of Least Square Method, I see some matrix calculus, which I have no clue. Can anyone explain to me or recommend me a good link to study this sort of matrix calculus? ...
4
votes
1answer
65 views

Help in Proving a theorem

For the last few days I am trying to prove Result 2 which I have written below that uses the concepts of matrix decompostions to write matrix $A$ in the block form. I need help to prove this ...
1
vote
1answer
371 views

Why SVD on $X$ is preferred to eigendecomposition of $XX^\top$ in PCA

In this post J.M. has mentioned that ... In fact, using the SVD to perform PCA makes much better sense numerically than forming the covariance matrix to begin with, since the formation of ...
0
votes
1answer
97 views

Solve: This System of equations for $X$ (does a real solution, exist?)

How can I solve $AX + diag(X)[I-c]=0$ for $X$? All matrices have real entries, $diag(X)$ is a diagonal matrix with the diagonal entries being the diagonal entries of $X$, and $c$ is a constant, real ...
1
vote
1answer
260 views

How to find the Householder transformation?

Assume $x=(1,0,4,6,3,4)^T$. Find a Householder transformation and a positive number $\alpha$ such that $Hx=(1,\alpha,4,6,0,0)^T$. I'm sorry that I don't know how to start with this problem. A ...
2
votes
2answers
172 views

A question about unitary matrix

We know that a complex square matrix V is unitary if \begin{eqnarray} VV^{*} = V^{*} V = I \end{eqnarray} I want to write matrix V into block matrix form, say $V = [V_1, V_2]$. My question is ...
1
vote
1answer
59 views

A basic question about convergence of matrix

I am confused with this very basic question. We know that for a square matrix A the following two properties are equivalent to A being a convergent matrix: 1: $lim_k\rightarrow \infty \|A^{k}\| = ...
1
vote
1answer
28 views

Conjuagate Gradient on Periodic BCs

I'm currently writing a CG solver. It works perfectly fine for Dirichlet boundary conditions, however, I also want it to work with periodic BCs. The problem I'm solving is a 3D Poisson equation. I ...
2
votes
0answers
72 views

Determinant error bound is better than norm bound for matrix product

In by textbook on numerical algebra, it states that for a numerical matrix product the error bound: $|A B - \hat{A} \hat{B}| \le c|A| |B|$ is a stronger expression than $\|A B - \hat{A} ...
0
votes
1answer
59 views

what we can say about block inverse besides schur complement

Suppose I have a matrix $M$, which has a block structure $% \begin{bmatrix} A & B \\ B^{T} & C% \end{bmatrix}% $, where A has the inverse. How can I better numerically calculate $A^{-1}B$ ? ...
0
votes
1answer
37 views

How do I get a matrix from a coordinate system?

What is the matrix of the reflection at the line $y = x-2$? How do I get the matrix at homogeneous coordinates? I don't get this question at all. I have really no idea of what I am supposed to do ...
2
votes
1answer
123 views

Relation between positive definite Hermitian matrices with their inverses

Let $A$ and $B$ be two positive definite Hermitian matrices. Show that the Hermitian matrix $$C\ =\ A^{-1} + B^{-1} - 4(A + B)^{-1}$$ is also positive definite. Thanks in advance.
0
votes
1answer
378 views

Column space of a matrix?

Recently I started learning about matrices and know for example that the pivot columns of a matrix form a basis for the column space of this matrix. I just can't seem to find out when two matrices ...
1
vote
2answers
64 views

Align basis of vector space with that of subspace

Suppose I have two real vector spaces $V,S\subset\mathbb{R}^n$ and $S\subset V$. Say the dimension of $V$ is $l$ and that of $S$ equals $m<l$. They are given in terms of their basis vectors $v_i, ...
1
vote
1answer
76 views

Eigenvalues of discretized linear integral operator

Suppose I have the following kernel operator: $Af(x) = \int_{-1}^1 K(x-y)f(y)dy$ which is also positive and compact. Hence, it has a countable set of positive eigenvalues. Suppose those eigenvalues ...
7
votes
1answer
229 views

Sum of idempotent matrices is Identity

[Ciarlet, Problem $1.1-10$] Let $A_k$, $1 \leq k\leq m$, be matrices of order $n$ satisfaying $$\sum_{k=1}^mA_k\ =\ I.$$ Show that the following conditions are equivalent. $A_k = ...
0
votes
1answer
180 views

QR Algorithm information

How can we perform 2 iterations of the QR Algorithm to the following matrix? $$A =\pmatrix{2 & -1 & 0 \\ -1 & -1 & -2 \\ 0 & -2 &3 ...
1
vote
0answers
126 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 ...
3
votes
2answers
1k views

When do two matrices have the same column space?

Recently I started learning about matrices and know for example that the pivot columns of a matrix form a basis for the column space of this matrix. I just can't seem to find out when two matrices ...
2
votes
0answers
39 views

maximal m-elements of the matrix inversion

Suppose the $n\times n$ matrix $A$ is invertible, and all its elements are between 0 and 1. The existing matrix inversion operation of $A^{-1}$ will take $O(n^3)$ time. Now I just want to find the ...
1
vote
1answer
103 views

Permutation Matrix

I need to find a Permutation matrix, for an E matrix, i have to permute it because i need to use always two of the rest of eigenvalues of matrix A to operate with them, matrix A is numerically defined ...
1
vote
0answers
61 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 ...
2
votes
0answers
43 views

Customising force-directed graph layout

I would like to implement a variant of the force-directed graph layout where some nodes are constrained to moving only along a predefined curve (e. g. circle). I looked at some implementations using ...
0
votes
0answers
101 views

Formula for distance travelled?

Given the coordinates of source of a missile, and those of the target both of which are on the surface of the Earth $(z=0)$ , I need to determine the total distance that the missile will need to ...
1
vote
1answer
134 views

Limiting Degrees of Freedom in 3D Point Registration

I'm search for some assistance in my application of Arun's algorithm for registration (fitting) of two 3D point sets using the Singular Value Decomposition: ...
0
votes
1answer
51 views

Gaussian Elimination Triangular Factoration

Factor $$\left[\begin{array}{ccc}1&4&0\\0&1&0\\0&3&1\end{array}\right]$$ into LU (L lower triangular and U upper triangular)
1
vote
3answers
49 views

How to LU facctorisation of a 4 by 4 matrice using gaussian eilimination!

I have a 4 by 4 matrice, A = [2 -2 0 0] [2 -4 2 0] [0 -2 4 -2] [0 0 2 -4] How would I use Gaussian Elimination to find the LU factorisation of the matrix Please could someone explain ...
1
vote
1answer
54 views

Hessenberg Matrices

$$A=\begin{bmatrix} 2&3&4\\ 3&-5&5\\ 4&5&0\end{bmatrix}$$ Find a unitary matrix $Q$ such that $A = QHQ^{H}$, where $H$ is Hessenberg. I am having a little trouble ...