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

learn more… | top users | synonyms

0
votes
0answers
23 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
22 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
66 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
11 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
33 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
84 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
44 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
27 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
67 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
86 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
17 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
55 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
17 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?
0
votes
0answers
28 views

How many kind of basis function to approximate an arbitrary function

I am finding a list algorithm to approximate an arbitrary function. Such as Bernstein, he said that a linear combination of Bernstein basis polynomials $$B_n(x) = \sum_{\nu=0}^{n} \beta_{\nu} ...
0
votes
0answers
35 views

Implementing specific SVD algorithms

My goal is to learn to implement the two-sided Jacobi SVD, a method of SVD for bidiagonal matrices, and a method of SVD for tridiagonal matrices. Can anyone recommend a place to learn about these, or ...
0
votes
0answers
31 views

How to implement QR method for bidiagonal matrices?

My goal is to take the singular value decomposition of a (not necessarily square) matrix. I have a method to do bidiagonalization of a matrix, and I can chop the bottom rows of zeros. In order to find ...
0
votes
0answers
78 views

Help understanding Jacobi SVD

I found this link, and I want to complete this implementation of the Jacobi SVD method, but it isn't clear to me how to implement alpha, beta, and gamma. I think it's very clear that ...
0
votes
0answers
7 views

Find rank-vital rows (coloops) of a matrix

Let $A$ be a $m\times n, m\geq n$ matrix over a finite field. Coloop is any row of $A$, such that the rank of $A$ is decreased when that row is removed. What is an efficient algorithm to find all the ...
0
votes
0answers
113 views

QR method for Hessenberg matrices

In trying to implement the method, my approach is to use a reduction to Hessenberg form, and then to iterate using a QR method of Givens rotations. However, I am having trouble successfully ...
0
votes
0answers
24 views

Generate duplicate element from a matrix by formula $b(i:j)=A(i:j,:) \times A^{-1} \times b$

I have an interesting question about generate duplicate elements from matrix. I assume that I have a matrix A (such as the bellow example $5 \times 5$) and vector $b$ is $5 \times 1$. My goal is make ...
0
votes
0answers
20 views

Help Required in eigenvectors for sparse matrix?

I have a large sparse matrix A(~400000,~400000) . If I randomly remove few rows from the matrix will there be considerable change in the eigenvalues and the eigenvector's compared to eigenvector's of ...
0
votes
0answers
44 views

Finding a function using first derivative

I have some data about just first derivative of a function. Also, I know a point of this function(e.g. (x1,y1)). How can I obtain the function? All my date are numerical. dev f(x)=[ 580.00 , 479.7308 ...
0
votes
0answers
40 views

Can someone explain how to obtain zeroes for L and U for A=LU factorization?

I understand that,In A=LU, for the L = lower triangular matrix, must have zeroes for all elements above the main diagonal and for U = upper triangular matrix, we need to have all elements as zeroes ...
0
votes
0answers
101 views

QR fatorization for tridiagonal matrices

Let $$A = \left[\begin{array}{rrrr} \delta_1&\gamma_2 & &0 \\ \gamma_2&\delta_2 &\ddots & \\ &\ddots &\ddots &\gamma_n \\ 0 & &\gamma_n ...
0
votes
0answers
33 views

the rank of QR decomposition

I saw this in a paper, where one has a QR decomposition $C=QR$ ($C\in R^{m\times r}$, $Q\in R^{m\times r}$ is column orthogonal, $R\in R^{r\times r}$, $m>r$). However, under the condition that the ...
0
votes
0answers
43 views

Iterated Schur complement for block matrices

Suppose you have got a symmetric block matrix $A = \begin{pmatrix} A_{1,1} & \dots & A_{1,n} \\ \vdots & & \vdots \\ A_{n,1} & \dots & A_{n,n} \end{pmatrix}$ Suppose that ...
0
votes
0answers
49 views

How to fit a stochastic matrix to given data.?

Given a data sequence of noisy observations of a 3-state Markov chain $X$ -- $y_1$,$y_2$,...$y_n$, with two transition matrices $A_1$ and $A_2$ corresponding to different regions (**) in the (unit) ...
0
votes
0answers
13 views

Powers of matrices via the generalised Lanczos process

At each iterative step of the generalised Lanczos process for the pair of matrices (A,B), we obtain the following factorisation: $$ A Q_k = B Q_{k+1} \widehat{T}_k, $$ where $Q_k^T B Q_k = I_k$ and ...
0
votes
0answers
49 views

Which of the following fixed point iterations will converge?

Which of the following fixed point iterations will converge? Why? Give the rate of convergence. (a) $x_{n+1} = \cos x_n$ (b) $x_{n+1} = \sin x_n$ (c) $x_{n+1} = \tan x_n$ For $10$ bonus ...
0
votes
0answers
26 views

Mixed Lognormal Model Calibration

Any ideas as to how to calibrate a mixed lognormal volatility model (Brigo and Mercurio 2002) for arbitrary N < 10? The paper seems vague with respect to implementation.
0
votes
0answers
274 views

Generalized SVD and weighted SVD

I've the following question: How should I select the $A$,$B$ matrices in the generalized singular value decomposition (GSVD) such that it solves the weighted version of the generalized singular value ...
0
votes
0answers
63 views

Finding the closest low rank correlation matrix?

I am looking to find the rank 3 correlation matrix approximation of a rank $n-1$ correlation matrix. This best approximation can be more clearly defined as the closest correlation matrix with rank 3 ...
0
votes
0answers
35 views

Does the Conjugate Gradient Method provide an eigenvalue estimate?

Suppose that we apply a Krylov subspace method to the linear system $A x = b$. For example, if $A$ is symmetric positive-definite, then the Conjugate Gradient method may be used. I remember that the ...
0
votes
0answers
46 views

Search Direction in Conjugate Gradient

Could you help me with a Conjugate Gradient question? In using CG to solve $Ax = b$, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous ...
0
votes
0answers
62 views

Induced matrix p-norm

Let $\|\cdot\|_p$ denote the $p$ norm $(p≥1)$ defined for every vector $x=(x_1,x_2,\ldots,x_n)^t\in\mathbb C^n$ by $\|x\|_p=(\sum|x_j|^p)^{1/p}$ and let $|||\cdot|||_p$ denote the matrix norm defined ...
0
votes
0answers
251 views

update cholesky factorization

I need to compute the Cholesky factorization of $H'H$ where $H$ is a big sparse rectangular matrix. After that $H$ is modified by adding several lines. That is H_n = [H ; line_1 ; ... ; line_n] in ...
0
votes
0answers
43 views

Is the following matrix Upper Hessenberg?

Does $$ A = \begin{pmatrix} 1 & 1 \\ -1 & -1 \end{pmatrix}$$ properly satisfy the definition of upper Hessenberg?
0
votes
0answers
43 views

Show that Newton’s Method is well-defined for all k and converges to 0 for $x_0>0$

Let $f : R → R$ with $f$ twice continuously differentiable, $\gamma > f''(x)>\delta, f(0)=0,f'(x)>\rho $ for $x ≥ 0$. Show that for any $x_0 > 0$ that Newton’s Method is well-defined for ...
0
votes
0answers
29 views

Jacobi Iteration with Shift

The question is to solve a linear system using Jacobi iterations with a shift of mu = 5. My code converges very quickly, but it does not yield the results that MATLAB gives with the backslash ...
0
votes
0answers
28 views

Applying perturbed matrix to unperturbed eigenvector

Suppose we've got a matrix $P$ and a perturbed version $\hat{P}=P+E.$ Given that $v$ is an eigenvector of $P$ with $Pv=0,$ I'd like to get as sharp a bound as possible on $\hat{P}v$ (in terms of ...
0
votes
0answers
313 views

Matlab project - Jacobi method for tridiagonal matrices…

I have to do a project in Matlab to my University and I don't quite understand what I should do. I was given script that solves systems of equations with Jacobi's method with given tolerance and ...
0
votes
0answers
35 views

Pairing Two Point Clouds

So I have two point clouds $X$ and $Y$ each with $N$ points in the familiar $\mathbb{R}^3$ euclidian 3D space. I then have an inter-point distance $d(\vec x_i,\vec y_j)$ which is zero if $\vec x_i$ is ...
0
votes
0answers
49 views

Relative Error with Respect to Frobenius Norm

I'm look at this tiny book called "Deblurring Images: Matrices, Spectra, and Filtering" by Hansen, Nagy, O'Leary. This is a self study, but I believe my question is broad enough so that it can be of ...
0
votes
0answers
110 views

Condition number perturbation

I have a matrix of the form $\tilde{H} = H + i A A^\dagger$. It is known that $H$ is hermitian and that $\tilde{H}$ is invertible and $A A^\dagger$ has a kernel of dimension $\geq 1$. I want to study ...
0
votes
0answers
58 views

Computing a few eigenvalues of large sparse nonsymmetric matrix without LU factorisation

I'm trying to find a few targeted eigenvalues of a large sparse (N=1e6,nnz=4e6) non-symmetric matrix. Currently I'm using MATLAB's 'eigs' function with the 'sigma' option and this uses the Shifted ...
0
votes
0answers
39 views

Recasting Ax=b to use SOR method

Just need some guidance as to how to recast the matrix equation equation $Ax = b$ so that I can produce an iterative matrix to perform Succesive Over Relaxation on. These matrices are $n x n$ I ...
0
votes
0answers
41 views

Are there any sure-fire methods for correctly arranging matricies for Gaussian Elimination?

I am attempting to make a Gaussian Elimination solver for systems of linear equations that contain less than 100 equations. I have roughed out a method for creating and filling in the diagonal of a ...