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

learn more… | top users | synonyms

1
vote
1answer
109 views

conjugate gradient method for semi definite case

Show for a symmetric, positiv semi definite matrix $A$, a vector $b\in Ran(A)$ and initial vector $x_0$: (1) All directions $d_0,d_1,...,d_m$ of the conjugate gradient method are in the range ...
0
votes
2answers
257 views

Definition of Spectral Radius / Eigenvalues of Product of a Matrix and its Complex Conjugate Transpose

For any matrix $\textbf{A}$, I know that in the Euclidean L2 induced/operator norm, $\|\textbf{A}\|=\sqrt{\rho(\textbf{A}^{*}\textbf{A})}$, with * being the complex conjugate transpose and $\rho$ ...
0
votes
0answers
56 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 ...
2
votes
1answer
35 views

Finding An Orthogonal Matrix

Let $u = (0,1,2,2)^{T}$, $v = (-3,0,0,0)^{T}$. Find an orthogonal matrix $A$ such that $Au=v$ and $A = I-B$, where $B$ is a matrix of rank one. I started by writing $A$ as $A = I - xy^{*}$ and using ...
0
votes
0answers
47 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
1answer
40 views

Psuedo-inverse of block low-rank, symmetric matrix?

I have a matrix that looks like $$ D = \left[ \begin{matrix} c_1aa^T & c_2ab^T \\ c_2ba^T & c_3bb^T \end{matrix} \right] $$ where $c_1, c_2, c_3$ are scalars and $a, b$ ...
1
vote
0answers
47 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}$ ...
2
votes
1answer
75 views

derivation of GMRES question: why is my result for the approximate solution to $Ax=b$ always exact?

I am trying to see if I understand the GMRES method and it's result. But somewhere I get confused and I wonder if I am making a mistake. We start with a system $Ax=b$. We look for approximate ...
0
votes
1answer
47 views

Rank of the evaluation of a polynomial matrix

Given a polynomial matrix $A(t)$ of rank $r$, I would like to know at what complex evaluations of $t$ the rank decreases. Some research with google told me these values are sometimes called the zeros ...
1
vote
1answer
60 views

Connection between results of two SVDs

Consider SVD of $M$: $$ M = U \Sigma V^\top $$ And SVD of $N= \ln M$: $$ N = U^\prime \Sigma^\prime V^{^\prime\top} $$ Anyone knows/has seen/can think of any interesting connection/relation between ...
0
votes
0answers
35 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 ...
3
votes
1answer
31 views

Is this a reasonable method of numerically comparing two matrix functions?

I am currently trying to compare two matrices with elements which are too complicated for me to algebraically show that they are equal element wise and I decided to try the following approach: ...
2
votes
0answers
36 views

Can the Lanczos algorithm converge very fast by taking a good initial guess?

Suppose I have the two lowest eigenvectors $v_1$, $v_2$ of a matrix $M$. If slightly change $M$ to $M'$. Can I use $v_1$ or $v_2$ as an initial guess for $M'$? If so, which one should be used, $v_1$ ...
0
votes
0answers
17 views

Properties of specific case of the gradient descent method

Consider the gradient descent method for the system $Ax=b$ where, $A=\begin{pmatrix}1 & 0 \\0 & a\end{pmatrix}, b=\begin{pmatrix}0 \\ 0\end{pmatrix}$ and the initial vector ...
0
votes
1answer
38 views

Why outer product isn't backward stable

Outter product isn't backward stable. This is because output matrix most likely has rank one and thus can't be represented in the form $(x + \delta x)(y + \delta y)^*.$ Also we know that if output ...
0
votes
3answers
29 views

Matrix Norm Division

Suppose $A=uv^*$ where $u$ is an $m$-vector and $v$ is an $n$-vector. For any $n$- vector $x$, we can bound $||Ax||_2$ as follows: $||Ax||_2 = ||uv^*x||_2=||u||_2|v^*x|\leq||u_2||||v||_2||x||_2$. ...
0
votes
1answer
94 views

Solve Bratu problem using Python

I am going crazy trying to solve the Bratu problem using Python: $$y''(x)+ e^{y(x)} = 0, \quad \lambda = 1, \quad x \in(0,1),$$ $$y(0) = y(1) = 0$$ I have to solve this using the tridiagonal ...
0
votes
1answer
52 views

Uniqueness of Thin QR Factorization.

Let $A \in \mathbb C^{m x n}$, have linearly independent columns. Show: If $A=QR$, where $Q \in \mathbb C^{m x n}$ satisfies $Q^*Q=I_n$ and $R$ is upper triangular with positive diagonal elements, ...
2
votes
2answers
41 views

How to show that $\| QA\|_2=\| A \|_2$ where $Q$ is unitary (for a matrix A)

I want to show that for a unitary matrix $Q$ and a matrix $A$ that $$ \|QA\|_2=\|A\|_2$$ I start with the definition of matrix induced norms: $$\| QA \|_2 = \sup_{x \neq ...
0
votes
1answer
54 views

What is the computational cost of reduced row echelon and finding the null space?

I'm taking computational linear algebra, and haven't been able to find too much information about the computational cost (in terms of m=rows and n=cols) of these two routines: Reduced Row Echelon ...
1
vote
1answer
64 views

The equivalence of numerical radius and spectral norm

Let $A$ be a $n\times n$ complex matrix. Define the numerical norm of $A$ as $$w(A)=\sup\{|x^*Ax|;\|x\|_2=1\}, \|x\|_2^2=\sum_{i=1}^n|x_i|^2.$$ And the spectral norm of $A$ is $$\|A\|_\infty ...
0
votes
1answer
9 views

What is and what represents a convergents function in polynomial form?

$$\mathbf{convergents}(cos(1), 20)$$ What exactly is a convergents function and what, that series of fractions is representing ? There is an use for this in numerical linear algebra ? Feel free to ...
2
votes
0answers
149 views

Optimized way to compute L1 distance matrix

I'm computing distances between two groups of multi-dimensional points giving a matrix of distances pairwise between points. For the L2 (euclidean) distance I can use optimized matrix multiplication ...
0
votes
2answers
35 views

Creating a random square matrix with known singular values

The first step in one question has me creating a random square matrix A with singular values given as $2^{-1}, 2^{-2}\dots 2^{-n}$. There is no other information about what assumptions can be made ...
1
vote
0answers
60 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 ...
1
vote
0answers
21 views

Speed of pseudo-inverse (with possibly ill-conditioned matrices)

I am computing the pseudo-inverse of several matrices of identical size $m \times n$ . However, computation (e.g. with the LAPACK pinv) seems to be much slower in some cases (5 to 10 times slower). ...
0
votes
1answer
32 views

An Inequality in Numerical Optimization

I am reading Jorge Nocedal and Sepher J. Wright's Numerical Optimization and stuck at an exercise 4.6 in chapter 4. The Canchy-Schwarz inequality states that for any vector $u$ and $v$, we have ...
2
votes
1answer
55 views

about the power of a matrix

Assume that matrix $A$ contains only 0 or 1 elements. Could anyone give me some condition, under which the matrices $A^i$ (for $i=1,2,3,...,k$) still contains only 0 or 1 elements. For example, I ...
7
votes
4answers
410 views

Solve quadric equation system

How to solve this analytically(not a numerical solution)? For given real and symmetric matrices $A_1,A_2,A_3,A_4\in\mathbb{R}^{4\times4}$ find $0\neq x\in\mathbb{R}^4$ $$x^TA_1x=0$$ $$x^TA_2x=0$$ ...
1
vote
2answers
296 views

Interpolation polynomial Challenge

suppose $p(x)=x^k-x^t, k \neq t $ (k,t is a positive integer). function q(x) be a Interpolation polynomial from degree lower or equal n, to data $i=1,...,n+1, (x_i ,p(x_i))$. if ----------- then ...
2
votes
1answer
50 views

Strictly diagonal matrix

Suppose that matrix $A$ is strictly diagonally dominant, show that $$\|A^{-1}\|_{\infty}\leq\left[\min_i\left(|a_{ii}|-\left|\sum_{\substack{j\neq i}} a_{ij}\right|\right)\right]^{-1}.$$
1
vote
1answer
105 views

Condition number - proof

I have a problem with which I've been struggling for a while. It's probably not that difficult, but I seem to be stuck so... here we are. Let A be an invertible lower- or upper-triangular matrix ...
1
vote
0answers
74 views

Saddle point problem (KKT) with block-diagonal matrix

Consider the following saddle point problem originating from an interior-point method algorithm: $$ \begin{bmatrix}\mathbf{H} & \mathbf{A}^{T}\\ \mathbf{A} & \mathbf{0} ...
0
votes
2answers
51 views

Euler method(path s1s2=s2s1)

Given a differential equation $\frac{dy}{dx}=f(x,y(x)), y(x_0)=y_0$. What is the condition for function of f(x,y) such that the result of $y(x_0+S_1+S_2)$ by using Euler forward method, a step size ...
0
votes
1answer
205 views

How do I find transformation matrix with respect to given basis in the domain and/or the codomain, given the transformation in the standard basis?

I´m being given a linear transformation, for which I can find the standard basis in the domain and codomain; but then, the book ask to find the associated matrix related to a new basis for the ...
0
votes
1answer
59 views

An algorithm of solving a non-homogeneous linear equation by random matrices

I'm looking for the proof of the following numerical algorithm. Suppose I want to solve a non-homogeneous linear equation \begin{equation} A x = b \end{equation} The matrix $A$ is non-invertible and ...
0
votes
1answer
45 views

Is it possible to optimize solution of this linear system?

I have a matrix of the form: ...
2
votes
2answers
100 views

How to prove the eigenvalues of tridiagonal matrix?

Assume the tridiagonal matrix $T$ is in this form: $$ T = \begin{bmatrix} a & c & & & &\\ b & a & c & ...
0
votes
0answers
39 views

matrix diagonalization without eigen decomposition, what other ways available?

I have a matrix, $A$ (it may be symmetric or asymmetric). I need to have a diagonal matrix without eigenvalue decomposition, please suggest what others ways are possible? Any new idea would be much ...
1
vote
2answers
103 views

Finding only first row in a matrix inverse

Let's say I have a somewhat large matrix $M$ and I need to find its inverse $M^{-1}$, but I only care about the first row in that inverse, what's the best algorithm to use to calculate just this row? ...
1
vote
1answer
52 views

Solve set of poorly conditioned linear equations in block matrix form

I would like to solve the following set of linear equations where A, B, C and D are each 4x4 matrices. K is then an 8x8 matrix The values in A and D have magnitudes of $\approx 10^{17}$, B has ...
1
vote
0answers
43 views

Write down a linear programming problem

I want to replicate a linear programming problem.I have the following information, for the background." A fuzzy regression analysis with only one independent variable X results in the following ...
2
votes
0answers
43 views

Lagrange multiplier for more than one constraints.

How to minimize $x^TAx$ over the set $D=(x\geq 0, x^TBx=1$ and $(I-A^\dagger A)x=0$), where $A$ is copositive matrix of order $n-1$ and $B$ is strictly copositive matrix of order $n$. If I drop the ...
0
votes
1answer
16 views

$\mathbb{R}^3$ to Planar Subspace Tranform

I'll ask my question three ways to try to maximize my chances of successful communication. I have: a point $P$ in $\mathbb{R}^3$ with coordinates $(P_X,P_Y,P_Z)$ a plane Defined by: a point '$O$' ...
1
vote
0answers
55 views

Solve linear system with matlab

In my problem, $A$ is a $m \times n$ matrix with $m \geq n$ and $\mathrm{rank}(A)= n$. Let $\Gamma$ be the $(m+n) \times n$ matrix defined by : $$ \Gamma = \begin{bmatrix} A \\ \mathrm{I_{n}} ...
3
votes
1answer
90 views

Generalized inverse/Pseudo Inverse

Let $A_{m. n}$ be a matrix with rank $p$ where $p\leq m$ and $p\leq n$. First Question: We need to show that $A$ can be decomposed as a product of two matrices $A=BC$ where $B$ is an $m$ by $p$ and ...
0
votes
0answers
32 views

computing leftmost eigenpair of positive-definite matrix

Let $A$ be an $n\times n$ real symmetric positive-definite matrix. Assume that $n$ is large and that $A$ is dense (i.e. it is not sparse). Question: What is the state-of-the-art algorithmically for ...
0
votes
0answers
49 views

Test for powers method

I have been told that for a normal matrix $A$, the powers method (i.e. computing the succession of Rayleigh quotients for a succession of vectors $z_k=A\cdot z_{k-1}$) can use the following stop ...
3
votes
1answer
193 views

Inverse of a diagonal matrix plus a constant

I am looking for an efficient solution for inverting a matrix in the following form: $D+aP$ where D is a (full-rank) diagonal matrix, a is a constant, and P is a one matrix. This question Inverse of ...
3
votes
2answers
155 views

How to efficiently solve a series of similar matrix equations using the LU decomposition

This is the problem I'm dealing with: Let $\sigma_1,\dots,\sigma_n \in \mathbb{R}$ and $b_1,\dots,b_n$ be column vectors of length $n$. Consider the system $$ (A - \sigma_jI)x_j = b_j, \quad ...