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

learn more… | top users | synonyms

1
vote
0answers
29 views

Numerical issues with matrix exponential for diagonalizable matrix

I am learning about computation of matrix exponentials, and have come across the technique: $$ e^A = U \operatorname{diag}(e^{\lambda_1}, e^{\lambda_2}, \ldots, e^{\lambda_n}) U^{-1}$$ Where the $\...
1
vote
0answers
16 views

$Q$ is perfectly conditioned with respect to the 2-condition number.

Show that if $Q$ is orthogonal, then: $||Q||_2 = 1$, $||Q^{-1}||_2=1$, and $\kappa_2(Q)=1$. Tell me if I'm wrong but, I'm at if $||QQ^T||_2 = ||I||_2$ then $||QQ^T||_2 = 1$ which implies that $...
1
vote
0answers
34 views

Is this a correct way to approximate a derivative

I have some function $S(\hat y)$ which I want to approximate its derivative with respect to a vector. It's a tad complicated, I'll try and explain. $S$ is a function of $\hat y$ only, but $\hat y$ is ...
1
vote
0answers
14 views

How to determine if an algorithm converges for solving Ax = b in practice?

Suppose I am using iterative refinement. I am updating the solution $$x^{(k+1)} = x^{(k)} +p$$ where $Ap = b - Ax^{(k)}$. If $A$ is ill-conditioned, then we can not simply use residual norm or the ...
1
vote
0answers
36 views

What is the function of the pivot index vector in Gauss Jordan Elimination with full pivoting?

In numerical recipes, on page 39 (page 4 of the pdf) the following algorithm has been suggested for finding a pivot: ...
1
vote
0answers
53 views

Dynamically equivalent of numerical solution of $y' = f(y)$.

Consider an autonomous system $y' = f(y)$ and a fixed step size $h$. a) Show that the trapezoidal method applied $N$ times is equivalent to applying first half a step of forward Euler, (i.e forward ...
1
vote
0answers
37 views

Galerkin formulation of 1D linear Schrodinger equation

I am interested in the weak (Galerkin) formulation of the 1D Schrodinger equation: $i u_t−\beta u_{xx}=0$ and $u(x,0)=u_0(x)$. As usual, we do integration by parts which yields: $i (u_t,v)+\beta (...
1
vote
0answers
53 views

Analytic Bounds for Eigenvalues of a 2x2 Block Matrix

I am trying to find conditions under which all eigenvalues of M will have nonpositive real part (i.e. M is negative semidefinite, I think). $$M = \begin{bmatrix} A & BE^T\\ CE & D\\ \end{...
1
vote
0answers
12 views

Numerical algorithm for largest Eigenvalue problem

I am dealing with calculating an eigenvalue problem for differential operator of order 4: $$ \alpha \cdot\Delta^2 u+\Delta u-\Delta(u\cdot u_p(x))=\lambda u $$ where $\alpha\in \mathbb{R}$, $\Delta$ ...
1
vote
0answers
33 views

Perturbation of a linear homogeneous equation system

Let $A$ be a $n\times(n+1)$ matrix, full row rank. Let $\tilde A=A+\Delta A$ be a perturbation of $A$, again with full row rank. I am interested what is known about bounds on the angle between the ...
1
vote
0answers
16 views

Non-linear ODE with diagonal matrix

I have a differential equation of this form: $\frac{dX}{dr}(r)$= M(r)X(r)$ + (\sum_{i}X_i) D(r)X(r)$ $X(r)$ is a size n vector. $M(r)$ and $D(r)$ are n x n matrices with $D(r)$ diagonal. They are ...
1
vote
0answers
30 views

Existence of Non-Commutative $4 \times 4$ Matrix Multiplication Algorithm

This paper by a Russian gentleman gives an optimal (?) algorithm for $3$ $\times$ $3$ matrix multiplication. It beats a previously known method by reducing the total number of discrete operations from ...
1
vote
0answers
19 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 $...
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 w}{|\...
1
vote
0answers
51 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 pseudocode)...
1
vote
0answers
250 views

GAXPY Operations

Let A ∈$R^2$, x ∈ $R^k$. Find the first column of M = (A − x1I)(A − x2I)...(A − xkI) using a sequence of GAXPY’s operations. GAXPY: General matrix A multiplied by a vector X plus a vector Y. I tried ...
1
vote
0answers
29 views

Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include: All vectors in $S$ All vectors in $T$ All vectors that can be ...
1
vote
0answers
38 views

Computational methods to minimizing the norm of a matrix monomial.

Linear optimization solves the problem $$\min_{\bf x}\{\|{\bf Ax - b}\|_2^2\}$$ Edit: Some clarification Doing the derivation of the optimum, first expand the norm: $$\|{\bf Ax - b}\|_2^2 = ({\bf ...
1
vote
0answers
42 views

How can I write $\prod\limits_{i = 0}^n {\left( {x - {x_i}} \right)} $ in terms of a polynomial as $\sum\limits_{i = 1}^n {{a_i}{x^n}} $?

How can I write $\prod\limits_{i = 0}^n {\left( {x - {x_i}} \right)} $ in terms of a polynomial as $\sum\limits_{i = 1}^n {{a_i}{x^n}} $? In the other words, is there a way to write $a_i$ in terms of $...
1
vote
0answers
26 views

Conditional expectation of a set of Gaussian variables

I was wondering if there is an efficient way to compute the conditional expectation of every element in a Gaussian random vector ? Specifically: For a pair of Gaussian random variables $[x,y]$, the ...
1
vote
0answers
40 views

How to apply Runge-Kutta to an implicit scheme?

I see there are some differences in the solution as I increase the resolution of my grid. I'm using Operator Splitting to solve Diffusion Reaction equation \begin{equation} \frac{\partial u}{\...
1
vote
0answers
21 views

Relationship between QR and LU factorization

Both algorithm return very similar results in terms of having a upper/right triangular matrix as one of the factors. What is the relationship between Q and L, and between R and U? What is the ...
1
vote
0answers
26 views

How can I solve this specific set of equations?

Here are the equations: $$\sum_{k = 1}^n i_k + Y_n u_n = J \quad \quad (1)$$ $$i_1 + Y(u_1 - u_2) = J \quad \quad (2)$$ $$i_k - Y(u_{k - 1} -2u_{k} + u_{k + 1}) = 0, \quad \quad k = 2, ..., n - 2 \...
1
vote
0answers
26 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 ...
1
vote
0answers
141 views

Numerically stable SVD

In this question regarding SVD, it is explained why eigen decomposition of $ A^tA $ is not numerically stable compared to "direct SVD algorithms". Since the former is the algorithm I'm most familiar ...
1
vote
0answers
46 views

Numerically finding eigenvalues of a Volterra operator of first kind

I'm looking for a solution to the following problem - $\int_{-\infty}^{\infty} K(x-y) f(y) = \lambda f(x)$ Consider $K(x-y) = \left\{ \begin{array}{lr} e^{-(x-y)} & : x > y \\ 0 & : x &...
1
vote
0answers
58 views

Ideas for expressing the inverse of matrix quadratic form $CAC^T$

I want to find an expression for the inverse of the matrix system $Z=CAC^T$, where $A \in \mathbb{C}^{n \times n}$ is block diagonal with dense blocks, and $C \in \{-1,0,1\}$ with dimension $m \times ...
1
vote
0answers
143 views

Eigenvalues after Givens-Rotation

Im just validating my own Code of a Givens-Rotation in Matlab. Therefore i let matlab compute the Eigenvalues after each Givens-Rotation. I am wondering why the Eigenvalues computed by matlab are ...
1
vote
0answers
61 views

Simplifying the Generalized Eigenvalue Problem

Let $\Sigma_1$, $\Sigma_2$ be symmetric positive-definite real $n\times n$ matrices. We want to solve the generalized eigenvalue problem $$ \Sigma_1V=\Lambda\Sigma_2V, $$ where $\Lambda$ is the ...
1
vote
0answers
77 views

complex rank-one update

I'm trying to find the eigendecomposition of a rank-one update to a complex matrix $D + uv^T$. The matrix $D$ is diagonal, but not the identity. It has unique imaginary entries along the diagonal. $uv^...
1
vote
0answers
57 views

Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay 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, i.e.,...
1
vote
0answers
24 views

Overdetermined system with discrete data.

The setup I have a set of experimental data (subscript 1) which calculates two variables $u_1(x,y,z)$ $v_1(x,y,z)$ I can calculate the three spatial gradients for my two variables ($u_1$ and $v_1$...
1
vote
0answers
54 views

QR Algorithm fails under certain conditions

First of all, i have to admit that i am really knew to this numeric stuff. I have to detect two complex Eigenvalues of a Matrix and therefor i implemented some easy QR-Algorithm with MatLab. I am ...
1
vote
0answers
42 views

$Az + B\overline{z}$ as a linear operator

Given two matrices $A,B \in \mathbb{C}^{n\times n}$ with fixed $n\in\mathbb{N}^+$, let us consider the operator $$ L:\mathbb{C}^n \to \mathbb{C}^n,\\ L(z) = Az + B\overline{z}. $$ This operator is not ...
1
vote
0answers
151 views

Row degeneracy in systems of linear equations

I am trying to understand the concept of row degeneracy in a system of linear equations, but having trouble understanding this problem. \begin{align} x+2y+z &= 2 \tag{1} \\ 2x+y+3z &=5 \...
1
vote
0answers
17 views

Enforcing additional constraints in linear equation

In a finite element context, I come up with a sparse "stiffness matrix" $A$ and a corresponding RHS $b$. The goal is now to solve $$Au = b$$ Where $u$ is a coefficient vector of the solution. Now I ...
1
vote
0answers
36 views

Solving System of Linear Equations

These are the two known equations: $$\frac{(I_2+I_3)-(I_1+I_4)}{I_1+I_2+I_3+I_4} = \frac{2x}{L}$$ $$\frac{(I_2+I_4)-(I_1+I_3)}{I_1+I_2+I_3+I_4} = \frac{2y}{L}$$ where I know the values of $(x,y,L)$. ...
1
vote
0answers
70 views

SVD of a block partitioned matrix

Given a block partitioned matrix $\boldsymbol{A}$ $$ \boldsymbol{A} = \begin{bmatrix} \boldsymbol{A}_{1,1} & \boldsymbol{A}_{1,2} & \cdots \\ \boldsymbol{A}_{2,1} & \boldsymbol{...
1
vote
0answers
428 views

Really confused about LU decomposition and Doolittle algorithm

I'm really confused about the Doolittle algorithm, so I need some help. At the end of the description at wikipedia, it says It is clear that in order for this algorithm to work, one needs to ...
1
vote
0answers
82 views

Question on the uniqueness of LU decomposition

Let $A \in \mathbb{K}^{n \times n}$ a matrix, and suppose that we can run the Gaussian elimination on $A$ without row or column interchange, so there exist the $LU$ decomposition of $A$. We define ...
1
vote
0answers
113 views

Using Cholesky factorization to solve the system AXA=B

I have been given a problem of solving X, which is an unblurred image, in the system: $$B = A X A \iff X = A^{-1} B A^{-1}$$ Where the matrix A describes the blurring of an image and the matrix B is ...
1
vote
0answers
57 views

Least-squares solution to a transformation between coordinate frames

Suppose I have four coordinate frames in 3D space: A, B, X and ...
1
vote
0answers
46 views

LU-factorisation of a square matrix

I need to show that the following matrix cannot be factor into the product LU. \begin{equation} A=\begin{bmatrix}1&2&-1\\2&4&0\\ 0&1&-1\end{bmatrix} \end{equation} I did the ...
1
vote
0answers
47 views

What's the point of 1-norm matrix estimation? Why not brute force?

Calculating (brute-force) 1-norm of a square matrix should take $O(n^2)$ operations, with a small factor involved. Apparently, there is an algorithm (link) for estimating 1-norm that takes $O(n^2 t)$ ...
1
vote
0answers
39 views

Is it better to compute $A^tA$ once and then $Ax$ several times or compute $y=Ax$ and then $A^ty$ every time?

So I have this algorithm which given a matrix $A$ it assigns $A=A^tA$ outside the loop and then on the algorithm loop it solves multiple instances of $Ax$ for different $x$s, (meaning that it's ...
1
vote
0answers
74 views

Rayleigh quotient ($|r(q)-\lambda|=O(||q-x||_2^2)$ ?)

how to show $|r(q)-\lambda|=O(\|q-x\|_2^2)$ $r(q)=q^*Aq/(q^*q)$ and $\lambda$ is an eigenvalue, $A$ is a Hermitian matrix. $x$ is the unit eigenvector corresponding to $\lambda$. and $q$ is a unit ...
1
vote
0answers
351 views

Meaning of singular Jacobian and workarounds to Newton's method

I'm currently working with Galerkin's method to solve differential equations and I have to retrieve unknown coefficients for the truncate expansion. This is just to set the background for why I need ...
1
vote
0answers
28 views

LU Decomposition for the solution of two linear systems

Let's say I have the following linear system: \begin{equation} \left[ \begin{array}{cccc} S&&L^{T}&&A^{T}&&0\\ L&&0&&0&&0\\ A&&0&&0&&...
1
vote
0answers
111 views

the Gauss-Jordan algorithm requires how many multiplications/divisions and add/subtractions

I am trying to show this following result. The Gauss-Jordan algorithm requires $\frac{n^3}{2}+n^2-\frac{n}{2}$ multiplications/divisions and requires $\frac{n^3}{2}-\frac{n}{2}$ additions/...
1
vote
0answers
69 views

Does this function have a unique fixed point?

Consider the following equations in fixed-point form: $$\mathbf{x}=F(\mathbf{x})=[f_1(\mathbf{x}),f_2(\mathbf{x}),\cdots,f_n(\mathbf{x})]^T$$ where the function $f_i$ is defined as $$f_i(\mathbf{x})=\...