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

learn more… | top users | synonyms

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
0answers
20 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 ...
0
votes
0answers
39 views

Find the inverse of $A+uB+vC+uvD+u^2E+v^2F$ where $A,B,C,D,E,F$ are symmetric.

Given scalars $u,v$ s.t. $0<u,v<1$, we seek the properties of the matrix defined by $$P=A+uB+vC+uvD+u^2E+v^2F$$ A is symmetric and positive definite. $B,C,D,E,F$ are symmetric, but might not ...
0
votes
0answers
10 views

How to find How to find ΔU if LU factorization of tridiagonal Matrix A is used to sovle system Ax=b?

How to find ΔU if LU factorization of tridiagonal Matrix A is used to solve system Ax=b? By using forward and back substitution to show that x̂ satisfies ...
0
votes
0answers
88 views

How to decide if a system is ill conditioned when the matrix condition number is very different for different norms?

A linear system Ax=b is said to be ill-conditioned if the condition number (A)of the coefficient matrix A is far from 1. Consider the system $$\begin{align}x_1 = &b_1 \\ x_1+x_2 = &b_2 \\ ...
0
votes
0answers
21 views

How to find Common (invariant) Subspace between more than two Hankel Matrices?

Note: I am not a mathematician but a control engineer. A general nonlinear $n_{a}^{th}$ order discrete-time state-space model is described by the following equations: \begin{align} ...
0
votes
0answers
20 views

Prove if a square root of a Herimitian positive semi-definite matrix is also Herimitian positive semi-definite, then it is unique.

Prove if a square root of a Herimitian positive semi-definite matrix is also Herimitian positive semi-definite, then it is unique. Here is what I have done so far: By the spectrum theorem, suppose ...
0
votes
0answers
28 views

LU Decomposition simplification on a tridiagonal matrix

If I have a tridiagonal matrix that looks like Tn = diag[1, 3, 1], I can do LU Decomposition of it using n - 1 multiplications (by omitting multiplications with 1) but not n - 1 divisions, right? In ...
0
votes
0answers
22 views

A problem about the condition number

Given that $I\in R^{n\times n}$ is identity matrix and $||I||=1$.Assumed that Matrix $A\in R^{n\times n}$ is nonsingular,with $\delta A$ satisfying $||A^{-1}||||\delta A||<1$. Then $A+\delta A$ is ...
0
votes
0answers
17 views

Question related to matrix transformation in sequence spaces.

Let $M=[K_{i,j}]$ be an infinite matrix, where $K_{ij}=1/i \text{ if } 1\leq i \leq j \text{ and } K_{ij}=0 \text{ if } i>j\geq 1$. Then $M$ defines a map $\ell^p \to \ell^r$ iff $p=1 \text{ and } ...
0
votes
0answers
14 views

convergnece of QR-method

I'm studying the QR-algorithm. In particular I have this algorithm: For every $k=0..n $ select a shift $\sigma_k$ factorize $A_k-\sigma_k I =Q_kR_k$ multiply $A_{k+1}=R_k Q_k+\sigma_kI$ muliply ...
0
votes
0answers
45 views

Compression of a matrix A by V

I can't understand and even can't find any text on Compression of a matrix A by V. meaning if $B=V^*AV$ then B is called the compression of A. What does it mean???
0
votes
0answers
41 views

Solving for intersection of line and a vector function.

How would one approach a problem of finding intersection points between a line $\vec l = \vec S + d \vec t$ and vector of the form $$\vec v = \begin{pmatrix} x \\ y \\f(x, y) \end{pmatrix}$$ I am ...
0
votes
0answers
35 views

Rapid calculation of eigenvectors for a submatrix when I know the eigenvectors of the full matrix

I have an $N \times N$ matrix $Z$ that is complex-valued and nonsymmetric in general. I can solve for the eigenvalues and eigenvectors of this matrix numerically. Call the diagonal eigenvalue matrix ...
0
votes
0answers
67 views

Extracting I-Vectors from a GMM-supervector

The probability model for I-vector in GMM-UBM system is : M = M(ubm) + Ty where, M is GMM supervector (means of all gaussian components concatenated in single vector) M(ubm) is UBM supervector I ...
0
votes
0answers
10 views

Response Matrix with finit actuator

I have a system of penalties ($P$) and actuators($A$). Whereby: d$P_i/$d$A_j$ = close to constant $\quad\forall i,j$ In order to minimize $P$, I create a response Matrix ($M$). With its ...
0
votes
0answers
48 views

Looking for references on the complexity of computation of a basis transformation matrix

I'm looking for some references on the complexity for the following kind of problem: Given two Basis $(a_1, ... ,a_n)$ and $(b_1, ..., b_n)$ of the $K(x)$-vector space $V$ I want to compute the ...
0
votes
0answers
23 views

Speeding up Conjugate Gradients iterations for Sparse Matrices?

I've been using Conjugate Gradients to minimize linear systems involving sparse matrices. Although many of my sparse matrices are highly specialized - i.e. for any given row it is easy to know which ...
0
votes
0answers
42 views

Finite difference: Radial symmetry boundary condition in tridiagonal system?

I am putting together an axisymmetric finite difference solver for Poisson's equation over a non-"rectangular" boundary in axisymmetric cylindrical coordinates. I was planning on using the dynamic ...
0
votes
0answers
29 views

Error bounds for solution of system of linear equations when coefficients are uncertain

I have a square system $Ax=b$ and would like to know how much the solution $x$ can change when I change the coefficient matrix $A$. I've stumbled upon the condition number, but this seems to apply ...
0
votes
0answers
27 views

What are some possible reasons for a large condition number?

For this question, please assume that I am talking about the condition number with respect to the spectral norm. That is, $\kappa_2(A) = \|A\|_2\|A^{-1}\|_2 = \frac{\sigma_{max}(A)}{\sigma_{min}(A)}$. ...
0
votes
0answers
12 views

Proof of QR Algoirthm Convergence

I am reading Trefthen and Bau and the amount of implicit proof steps are killing me. Can someone explain how the statement of convergence for the "pure" QR Eigenvalue Algorithm (Theorem 28.1) is ...
0
votes
0answers
18 views

how to project optimal parameters on to feasible region

Hi: I'm trying to understand the concept of projection and I created a toy example that might help me to do that. Suppose that I have a non-linear optimization with 3 parameters theta_1, theta_2 and ...
0
votes
0answers
36 views

Parametrization of the $Ax=b, x \geq 0$ domain for Monte-Carlo simulation

I have a linear system, $n=15$, with $6$ constraints. There's no problem finding a single solution or establishing the null space; so I can see the full solution space. But I'm only interested in ...
0
votes
0answers
12 views

Linear Relationship of two equations

if $0.46a = 120b$ and $2.68a = 60b$ The relationship is linear. what does $0b$ equal in terms of $a$? what does $1b$ equal in terms of $a$? A method to work this out would also be nice, I have ...
0
votes
0answers
71 views

Most stable algorithm to solve a system of linear equations?

I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to ...
0
votes
0answers
25 views

What is the source of the error in the Sherman-Morrison formula application?

The Sherman-Morrison formula results in small errors in relation to the standard matrix inverse operation after each application, as shown here. From what I understand, the Sherman-Morrison identity ...
0
votes
0answers
38 views

How to calculate $det(X^T X)$ efficiently, update one column of X each time

$X_{1} = (A, b)$, where $X_{1}$ is a $n\times p$ matrix, $A$ is a $n\times (p-1)$ and $b$ is $n\times1$. First calculate $\det(X_{1}^T X_{1})$, then update $b$ with $c$, st. $X_{2} = (A, c)$ and ...
0
votes
0answers
56 views

Efficient method to compute grand sum of a Vandermonde matrix?

Is there a computationally efficient method to calculate the sum of all elements (grand sum) of a Vandermonde matrix? Each row can be quickly calculated using the formula for a geometric progression. ...
0
votes
0answers
29 views

Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

I have the following quadratic form I need to evaluate: $x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors. Now assume that I am given for free both $A^{-1}$ ...
0
votes
0answers
56 views

Approximation of Mahalanobis distance

If $A$ is a symmetric positive definite $n\times n$ matrix then the square Mahalanobis norm of a vector $v\in \mathbb{R}^n$ is given by $$\lVert v \rVert_A^2=v^t A^{-1} v.$$ Now I have a situation ...
0
votes
0answers
73 views

Proof that Householder Triangularization for QR is backward stable

How do you prove that QR factorization via Householder Triangularization is backward stable? Theorem 16.1 (From Trefethen and Bau): Let the $QR$ factorization of a matrix $A$ be computed by ...
0
votes
0answers
23 views

Linear algebra <perhaps an application of Gordan' Theorem>

Question. Let $a_1,...a_n\in\{0,1,-1\}^m$ and $\sum a_i=(1,...,1)$. Is there a permutation $\tau$ of $\{1,...,n\}$ Such that for each $k\in \{1,...,n\}$ the vector $\sum_{i=1}^k a_{\tau (i)}$ has ...
0
votes
0answers
24 views

Is my QZ-Step as postulated in the paper?

I am working with the paper An algorithm for generalized matrix eigenvalue problems from C.B. Moler and G. W. Stewart (paper available here: ...
0
votes
0answers
24 views

QZ-Algorithm: how to simultaneously generate the upper triangular form

I need to calculate the Eigenvalues of a generalized Eigenvalue Problem. To achieve this, i wanted to use the QZ-Algorithm, which avoids calculating the inverse of a Matrix. This quite useful, because ...
0
votes
0answers
73 views

Givens-Rotation from the right

i need to get a Givens-Rotation, which zeros a matrix entry when multiplied from the right side. I did already look at this topic givens rotation from right side but i could not really understand the ...
0
votes
0answers
13 views

Conversion of cylindrical harmonic field into space-harmonic field for plane waves

It is well known that a plane wave can be represented by an infinite sum of cylindrical wave function of the form $\varphi^i(\rho,\phi)=e^{\left(-j\beta \rho ...
0
votes
0answers
43 views

PCA when SVD is a skinny SVD

A = m * n matrix. When $m \ge n$, it is easy to see that the V matrix in the full SVD ($A = U*S*V^T$, where U and V are both orthonormal square matrix) and V in a skinny SVD are the same. When $m \lt ...
0
votes
0answers
43 views

Solving the linear system $XL + L^TX = M$ efficiently

I'm wondering of an efficient way to solve the following system for the symmetric matrix $X$, given a positive semi-definite matrix $S$ and any matrix $M$: $$ LL^T = S $$ $$ XL + L^TX = M $$ $$ (XL) + ...
0
votes
0answers
98 views

When to use iterative methods for solving systems of linear equation

Iterative methods such as Jacobi, Gauss-Seidel method and successive over relaxation have a very limited field of use - for diagonally dominant matrices. So how they could be used on practice? What is ...
0
votes
0answers
45 views

Implicit Solution of Linear Algebraic Equations with Discontinuities

I am trying to get a reliable algorithm for solving a set of linear algebraic equations involving implicit singularities/discontinuous function. The model equation is: $$ {\bf s}_{n+1} = {\bf s}_n ...
0
votes
0answers
29 views

Smallest square problem, $A^*A$ singular?

In our numerics class, we have to solve the smallest square problem $Ax = b$ with $$A = \left( \begin{matrix} 1 & 3 &-4\\ 3 & 9 & -2\\ 4 & 12 & -6\\ 2 & 6 & 2 ...
0
votes
0answers
17 views

Linear Inverse Problem with symmetry constraint

I'm not entirely sure if this is even a solvable problem: $\mathbf{A} = \mathbf{B} \mathbf{C}$ Knowns: $\mathbf{A} \in \Bbb{R}_{n\times m}^{+}$, $\mathbf{B} \in \Bbb{R}_{n\times m}^{+}$ An ...
0
votes
0answers
75 views

Determining Nullspace Basis so that only one column is deleted or added as a row is added or deleted, with remaining columns of basis staying the same

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, ...
0
votes
0answers
125 views

the SVD (singular value decomposition) of an augmented matrix

Suppose we have a $4\times 3$ dimensional matrix $A$. Denote the SVD of $A$ by $USV^T$, where $U\in R^{4\times 3}, S\in R^{3\times 3}, V\in R^{3\times 3}$. Then, we construct a new matrix $B=[A;0]\in ...
0
votes
0answers
25 views

Upperbound for a linear algebraic ratio?

Consider ($n\times 1$)-column vector $\mathbf{p} = (p_i)_{i=1}^n$ with $p_i > 0$ and a symmetric ($n\times n$)-matrix $\mathbf{A} = [a_{ij}]$ with $a_{ii} = 0$ and $a_{ij} \in [0,1]$ for $i \neq ...
0
votes
0answers
19 views

Backwards Stability of systems

Let $A$ be a nonsingular matrix, let $x_{k+1}$ be an approximation to the solution of $Ax=b$, and let $r^{k+1}=b-Ax^{k+1}$. Show that $x^{k+1}$ is $\epsilon$-backward stable approximate of ...
0
votes
0answers
60 views

Linearize discretized nonlinear system model

For the following nonlinear system I want to find the linearization after a discretization: $$ \begin{pmatrix} \dot{x_{1}} \\ \dot{x_{1}} \\ \dot{x_{1}} \end{pmatrix} = 1/A \begin{pmatrix} ...
0
votes
0answers
18 views

sparse, complex, unymetric test-matrix

Can anybody recommend me a sparse, complex, unsymmetric test-matrix (maybe from MartixMarket) which is solvable with a transpose-free QMR without preconditioning in under 1000 iterations?