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

learn more… | top users | synonyms

2
votes
1answer
87 views

Inverse of constant matrix plus diagonal matrix

Is there an efficient way to calculate the inverse of an NxN diagonal matrix plus a constant term? I am looking at N of around 40000. $\left[\begin{array}{cccc} a & b & \cdots & b\\ b ...
2
votes
1answer
67 views

Linear equation: $(A^\top A+B^\top B + D)x=c$ where $A,B$ are structured sparse and $D$ is diagonal.

Updated: the goal is to solve $(A^\top A+B^\top B + D)x=c$. Maybe it is not necessary to compute $(A^\top A+B^\top B + D)^{-1}$. Denote $e=(1,1,\ldots,1)^\top\in\mathbb{R}^n$ and ...
1
vote
1answer
41 views

Consistency of the system $AX=b$

In the concept of consistency (compatibility) of a matrix, when $b \in \mathbb R (A)$ we know for sure that the system is consistent or there may exists no solution for it? But when $b \notin \mathbb ...
0
votes
2answers
28 views

Formatting Linear equation

How do I craft a linear equation so that it is in the form of $ax + bx + c = 0$ where $a^2 + b^2 = 1$ if I have two points? I know how to get it into the form $ax + bx + c = 0$ but I can't figure out ...
1
vote
0answers
29 views

Check feasibility of a system of integer linear equations

I'm currently working on a very large integer linear programme which cannot be solved within any reasonable time. The initial set of linear equations S={Ax<=b) is feasible. I want to add more ...
2
votes
0answers
47 views

Effective computation of matrix commutator

Is there a faster way to compute the commutator of large (at least one of them sparse) matrices $[A,B]$ then to compute $AB$ ,$BA$ and subtract them?
1
vote
0answers
31 views

Influence of preconditioning on degenerate eigenvectors

I'm using a hierarchical decomposition of a sparse matrix $A$ as suggested here. I find that the method essentially finds eigenvectors using the QR algorithm. $A$ has some eigenvalues with ...
1
vote
0answers
69 views

Newton's method for multidimensional functions

Can Newton's method be used to find the root of a function f : $\mathbb{R}^n\to\mathbb{R}^m$. Can anyone provide a proof for this? (I have checked the method of solving system of equations with ...
1
vote
1answer
56 views

Efficient method for determining to the most positive eigenvalue of a matrix

I am trying to implement an algorithm that requires knowing the largest $\textbf{positive}$ eigenvalue of a $\textbf{real symmetric, non-sparse}$ matrix and the corresponding eigenvector. The actual ...
0
votes
0answers
29 views

What is the largest (dense, real, symmetric) random matrix I can diagonalize on a computer?

I have read that 10.000x10.000 is no problem for LAPACK or similar routines. I would like to know if N=20.000 or 40.000 is possible. EDIT: I don't know if it is relevant, but the matrix is positive ...
0
votes
0answers
34 views

Strange Convergence of SOR/Gauss-Seidel

I am having trouble with the convergence of my Gauss-Seidel/SOR method. The matrix $A$ in $Ax=y$ seems to be positive-(semi)definite. Its eigenvalues are: However, the method (SOR) improves the cost ...
1
vote
0answers
30 views

Change in Singular Value Decomposition of a matrix on addition of a single row

Given that I know the svd decomposition of a matrix, is there any way to compute the svd decomposition of the matrix obtained by adding a single row to the original matrix? Is there any relation ...
1
vote
0answers
31 views

If symmetric matrix in a least-square deconvolution problem positive definite?

I want to apply Gauss-Seidel method in a least square deconvolution problem. The convolution of two vectors is written in: $h * x = z$. $$z(n) = \sum_{i=0}^{N-1}h(i)x(n-i)$$ It is a linear transform ...
1
vote
1answer
33 views

How to recover Q from the (tiled) QR decomposition using householder factorisation?

I'm trying to implement the tiled QR decomposition in MATLAB (in an attempt to understand it), and I'm trying to check that my SGEQRF (upper corner tiles) function is working correctly. I have a ...
0
votes
0answers
38 views

How to find a transformation matrix T?

(1.) Suppose there is matrix C of dimension "p by n" where p is less then n i.e. p I want to know is there any particular way exist to find transformation matrix T of dimension "n by n" such that ...
0
votes
2answers
37 views

Eigenvalues and eigenvectors of a matrix

We know that if $\lambda (\neq 0)$ is an eigenvalue of a matrix $A$ corresponding to eigenvector $X$, then $\dfrac{1}{\lambda}$ is an eigenvalue of $A^{-1}$. But whether the corresponding eigenvector ...
0
votes
0answers
21 views

Orthogonal polynomials induction proof

I tried writing this all out but cannot seem to get anything sensible. Basically I want to prove that assuming w(x) is the weight function of a Gram Schmidt orthogonalization process and w is an ...
2
votes
1answer
80 views

Matrix Norm Inequalities and Linear Least Squares

I am working through one of my universities old QUALS and came across the following problem: Let $A,E\in \mathbb{C}^{m\times m}$. Suppose that $\sigma_\min>0$ is the smallest singular value of ...
0
votes
2answers
48 views

Is this Gram-Scmidt (or an application of) it?

I am given a $2\times 2$ matrix $$\left[ \begin{array}{ccc} a & 0 \\ 0 & b \\ \end{array} \right] $$ where $a,b \in \mathbb{R}$. I was told than an orthnormal basis for the colums of this ...
0
votes
1answer
65 views

Matrix with constant row sum

It is well known (and shown several times on this site) that if we have a matrix so that each row sums to zero then the matrix must be singular. I am curious if the following partial converse is ...
3
votes
1answer
116 views

Prove $|\det A| \leq \prod_{j=1}^n ||a_j||$

Let's say A is a square n by n matrix. ||$x$||=$x^T x$ and x is a real n-column norm. How would you show this? I tried to use the QR factorization here in showing that ||$a_j$||=||$r_j$||, but ...
1
vote
1answer
22 views

Question regarding Givens Rotation

I need to solve the following equation using Givens Rotation: $$ A\cdot x = b $$ Correction: I need to solve: $$ ||A\cdot x - b || \to \min $$ with $$A = \begin{bmatrix} 1 & 1 \\ -2 & ...
1
vote
2answers
131 views

Trace minimization of a matrix

Suppose $S = \pmatrix{1&1\\ 1&0\\ 0&1}$, $W$ is a $3\times3$ covariance matrix, which could be regarded as fixed. I need to find a $2\times 3$ matrix $Q$ that minimizes $$ ...
3
votes
1answer
217 views

Numerical verification of solution.

I have the non-linear equation \begin{align} &\left( {x}^{2}-1 \right) \left( -\frac{1}{4}\left({\frac { \left( 4\,{x}^{3}+2\, ex \right) ^{2}}{ \left( {x}^{4}+e{x}^{2}+f \right) ...
1
vote
2answers
44 views

How to figure out the spectral radius of this matrix

$$A=\begin{array}{ccc} 0 & 1/2 & 0 & \cdots & 0 \\ 1/2 & 0 & 1/2 &\cdots& 0\\ 0 & 1/2 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots &\ddots ...
1
vote
0answers
54 views

Numerical algorithm to solve quadratic eigenvalue problem.

Given the equation $$-4 \left(a^2+a (n-1) (2 t^2-1)\right) \left(\sum _{i=0}^n \alpha_i t^{2 i}\right)^2 \\ +\frac12 \left(\sum _{i=0}^n \alpha_i t^{2 i}\right) \left(t \left(8 a (t^2-1)+1\right) \sum ...
0
votes
1answer
46 views

Avoiding gimbal lock

I am not really sure if I understand the phenomenon of gimbal lock correctly. Say I have a vector $\begin{pmatrix} x\\ y\\ z \end{pmatrix}$. And I want to keep the vector's length fixed but move it ...
1
vote
1answer
103 views

Norm of Block Diagonal Matrix

Given a matrix $A \in R^{m \times n}$ with known upper bound on the operatornorm $\| A \|$ I want to find an upper bound for the operator norm of the square root of the following matrix that is given ...
7
votes
1answer
189 views

Fast algorithm for approximating Eigenvalue distribution of large sparse matrix

I am interested in the eigenvalue distribution of a huge $2^{16}$x$2^{16}$ Hermitian sparse matrix with spectrum contained in $[-1,1]$. That is I don't need to know all eigenvalues exactly, but rather ...
1
vote
1answer
71 views

Proof that eigenvector corresponding to simple eigenvalue is continuous

Let $\lambda$ be a simple eigenvalue of $A \in L(C^n)$ and let $x$ be the corresponding eigenvector. Then for $E \in L(C^n)$, $A+E$ has an eigenvalue $\lambda(E)$ and an eigenvector $x(E)$ such that ...
1
vote
1answer
25 views

linear systems&normalize

suppose $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ be a linear function which can be represented by a $n \times n$ matrix. Then the jacobian of $f$ is the same as the function for $f$. But I now want ...
0
votes
0answers
39 views

Kalman Filter Predict Update of LDL Decomposition of a Covariance Matrix

From the state predict equation: http://en.wikipedia.org/wiki/Kalman_filter# $$P_{n+1}=AP_nA^T + Q$$ Suppose the $LDL^{T}$ ( http://en.wikipedia.org/wiki/Cholesky_decomposition#LDL_decomposition_2 ) ...
1
vote
0answers
19 views

Algorithm for finding only the $k$-th singular vectors

I know that we have truncated SVD that can compute the first say $k$ largest singular values (and corresponding singular vectors). However, I'd like to know if there is an algorithm that can find only ...
1
vote
0answers
44 views

Best way to solve specific block-tridiagonal linear system (10000x10000 and larger)

To provide more context, this system came from energy balance equation on a mesh with (n,m) nodes in each direction. It's a linear system that looks like this (size of system in blocks n = 4, size of ...
0
votes
1answer
42 views

Induced Matrix Norm

I have trouble following a proof of the induced Norm $||\cdot||_1$ The proof can be found here: ...
0
votes
0answers
18 views

Maximal angle between kernel of rows of a matrix

Consider a matrix with 2 columns $$ \begin{pmatrix} a_1 & b_1 \\ a_2 & b_2 \\ a_3 & b_3 \\ \vdots & \vdots \end{pmatrix} . $$ To each row $(a_i \;\;\; b_i)$, one draws the kernel ...
2
votes
1answer
127 views

Check if the following gradient is correct

This question regards the verification of the gradient of a given function. Notation. Let $N, K \in \mathbb{N}_0$ be given (nonzero) integers, with $K > N$. Let $\mathbf{x} = [x_b \ y_b \ z_b]^T ...
0
votes
1answer
24 views

How to evaluate the accuracy for sparse linear system solver

I'm currently trying to do some experiments on linear solver. However, it's a little hard to get the sense of the numbers. For example, I know large condition number is bad, but how large is bad? ...
2
votes
1answer
57 views

Least squares problem with orthonormality constraints

Given $y_1,\ldots,y_n\in \mathbb{R}$,$w\in \mathbb{R}^d$, and $x_1,\ldots x_n\in \mathbb{R}^D$, how do we solve the following optimization problem \begin{align} \min_A \sum_{i=1}^n (y_i-w^TA^Tx_i)^2\\ ...
2
votes
1answer
241 views

equations solved with Newton's method by finding the zeros of functions?

I found this statement in one paper I read recently: This problem can be solved by finding the zero of functions: ...
0
votes
0answers
28 views

Not enough memory for GMRES

After realizing that Gauss-Seidel is extremely slow for my simulation, i wanted to try GMRES and luckily found the C++ code here without diving into the theory. The size of the matrix in my case is ...
1
vote
1answer
40 views

QR decomposition error

How to find $$||A - QR||_2$$ without finding Q matrix (A is matrix, QR - qr decomposition of A) I have written a code which return only R (using Householder transformation).
1
vote
2answers
229 views

Gauss-Seidel method convergence algorithm

From Wikipedia: The convergence properties of the Gauss–Seidel method are dependent on the matrix A. Namely, the procedure is known to converge if either: ...
2
votes
1answer
120 views

Finding vector $x$ so that $Ax=b$ using Householder reflections.

Assume $n\times m$ matrix $A$ and vector $b$ are given. I am looking for $x$ that satisfies $Ax=b$ in terms of linear least squares problem. Let $A=\begin{bmatrix} 1 & 1 & 1 \\0 & 1 & ...
1
vote
1answer
136 views

block matrix multiplication

If $A,B$ are $2 \times 2$ matrices of real or complex numbers, then $$AB = \left[ \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right]\cdot \left[ \begin{array}{cc} b_{11} ...
1
vote
0answers
34 views

Solving a linear equation with a moderatly sparse 1000000*1000000 symmetric matrix

I've got a linear equation $A_{n*n}\cdot x=1_n$, where $n=1000000$ and $A$ is symmetric with approx $1000$ nonzero entries in each column and row. What would be the best numerically stable algorithm ...
2
votes
1answer
54 views

fast multiplication for a matrix and its transpose.

I know Strassen and other methods can achieve better than $O(n^3)$ for general square matrix multiplication. I am curious of the spacial case where the multiplication is between a $n*m$ matrix $A$ ...
1
vote
1answer
126 views

Proof that Newton Raphson method has quadratic convergence

I've googled this and I've seen different types of proofs but they all use notations that I don't understand. But first of all, I need to understand what quadratic convergence means, I read that it ...
3
votes
1answer
54 views

Spectral norm of symmetric matrices only with the diagonal, the first column, and the first row non-zero

Consider a real symmetric matrix $$\mathbf{M}=\left[\array{a_0&a_1&a_2&\cdots&a_n\\ a_1&b_1&0&\cdots&0\\ a_2&0& b_2&\cdots&0\\ \vdots &\vdots ...
0
votes
1answer
61 views

Is this matrix guaranteed to be positive-definite?

(This question pertains to a larger model proposed in this SIGRAPH paper, but I've pulled out the pertinent question and generalized it.) Let's say I have two large matrices $M$ and $L ...