{numerical-linear-algebra} questions involving algorithms for linear algebra computations.

learn more… | top users | synonyms

-1
votes
0answers
83 views

Show: Real roots of a polynomial [on hold]

I´ve got some problems with this task I found in a german script. Be $\ N \in \mathbb{N}$. Define matrix $\ \Pi := (\pi)_{0\leq i,j \leq N}$ with \begin{equation} \pi_{i,j} := \binom{N}{j} p_i^j ...
-1
votes
0answers
27 views

Improvement of Minimum description length (MDL) estimate [on hold]

I earnestly request apology if this question is inappropriate for the forum. The question has two parts one technical and the other is not technical. I would appreciate any response. Let me consider ...
0
votes
0answers
20 views

Global and local maxima in a weighted sum of logarithms of linear functionals?

Initially posted on math.stackexchange, was recommended that this is a more relevant forum: Is is possible to describe, and locate efficiently, the maxima of the function below in the parameters ...
2
votes
0answers
33 views

Global error estimates for numerical solutions of ODEs in Matlab or Mathematica [closed]

I need to find the first zero (smallest positive root) of the solution of the initial value problem $ry''+y'+f(r)y=0, \ \ y(0)=y'(0)=1$ for certain $f \in C^{\infty}(R)$. One can easily use ...
0
votes
0answers
75 views

Hadamard / matrix product adjoint

First of all I would like to thank everyone over here at mathoverflow for their amazing generosity and help (for both pros and newbies like myself). I apologize if this question seems dumb; I'm a new ...
3
votes
2answers
159 views

What are interesting heuristics of determining how far given matrix is from a singular one?

The condition number and volume of matrix (defined as absolute value of its determinant) are things which come to mind. Is there more? I think that over the years numerical folks (who are faced with ...
1
vote
0answers
64 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) ...
3
votes
0answers
28 views

Quasi-M matrices?

Does any body know a reference on lower triangular matrices with negative entries everywhere except for the diagonal and subdiagonal where entries are positive (when all entries are negative with ...
0
votes
0answers
45 views

Bits of precision matrix reconstruction

We have a real rank $r$ matrix $M\in\{0,1\}^{n\times n}$. Suppose we have diagonalized using $LMR=D$. I want to recover a real matrix $\widetilde{M}$ such that maximum absolute entry of ...
0
votes
0answers
42 views

Way to parameterise sparse multi diagonal matrix

I have an NxN matrix S that looks like this: $$ S^{-1} = K^{-1} + \Lambda $$ where N is a multiple of 3, both K and S are positive definite matrices, and Lambda is $$ \Lambda = \begin{bmatrix} x ...
0
votes
0answers
20 views

Column Subset Selection implementations

Are there readily available implementations of algorithms for the CSSP - Column Subset Selection Problem?
1
vote
1answer
80 views

QR decomposition of matrix [closed]

I have matrix $M = \begin{pmatrix} A & B \\ B^T & 0\end{pmatrix}$, where $A$ is $N\times N$, $B$ is $N\times 2$ and I have $Q$, $R$ such that $A = QR$. What is the fastest way to find $Q'$ and ...
4
votes
2answers
364 views

Eigenvectors of a symmetric positive definite Toeplitz matrix

I wish to efficiently compute the eigenvectors of an n x n symmetric positive definite Toeplitz matrix K. A full eigendecomposition would be even better. Although I assumed this would be a well ...
6
votes
2answers
171 views

Conditions for convergence of Euler's method

It is known that a sufficient and necessary condition for $$\dot y(t) = f(y(t), t), \quad t > 0, \quad y(0) = y_0$$ to have a unique solution is $f$ Lipschitz in $y$ and continuous in $t$. However, ...
2
votes
1answer
165 views

Linearly constrained eigenvalue problem

Suppose I'd like to: \begin{align} \mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\ \text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\ && ...
1
vote
1answer
59 views

Looking for algorithms based on sorting [closed]

i am looking for algorithms which use sorting in low-dimensional space like $R$ and how they are generalized for higher-dimensional spaces like $R^2$ where there is no sorting possible. (i.e. numbers ...
7
votes
1answer
157 views

Compute only selected components of an eigenvector

I am wondering whether it is possible to compute portions of the eigenvectors of a given (possibly very big) matrix. More formally, consider the eigenvalue problem $\mathbf{Ax} = \lambda \mathbf{x}$, ...
0
votes
1answer
172 views

Proving that the eigenvalues of a certain matrix product are positive

Let $A$ be an $m \times n$ matrix, and define: \begin{align*} U &= {\rm diag} \{ \frac{1}{\beta_j} \}, \beta_j = \sum_{k=1}^m |a_{kj}|, j = 1 \dots n \\ V &= {\rm diag} \{ \frac{1}{\alpha_i} ...
2
votes
2answers
170 views

Matrix, singular values, Moore-Penrose-pseudoinverse

If A is any real mxn-matrix consider the block matrix $\begin{pmatrix} E&A^T \\ A&0\end{pmatrix}$. This matrix seems to have close connections with pseudo inverse, svd etc. which are probably ...
4
votes
1answer
80 views

Sensitivity of the range of a matrix

The distance between two subspaces $\mathcal{U}$ and $\widetilde{\mathcal{U}}$ is classically defined as $d(\mathcal{U},\tilde{\mathcal{U}}):=\|P-\tilde{P}\|$, where $P$ and $\tilde{P}$ are orthogonal ...
5
votes
3answers
173 views

Norm of triangular truncation operator on rank deficient matrices

Let $T_{n\times n}$ be a triangular truncation matrix, i.e. $$T_{i,j}=\begin{cases}1 & i\ge j\\ 0 & i<j \end{cases}$$ It is known that for arbitrary $A_{n\times n}$ $$\|T\circ ...
1
vote
1answer
168 views

Are there some algorithms to solve the diagonal matrix $X$ to the following matrix equation?

Suppose $X$ is an unknown $m \times m$ diagonal matrix. Given a scalar $0<c<1$, and a matrix $A$ of $m \times m$ size whose entries $0<A_{i,j}<1$. Are there some algorithms to find the ...
2
votes
2answers
263 views

Solving a matrix equation $X=c \cdot AXA' +I$ with a diagonal corrections

I am now struggling to solve the matrix $X \in R^{n \times n}$ in the following equation: $X=c \cdot AXA' - diag(c \cdot AXA')+ I$, where (1) $A \in R^{n \times n}$ is a given matrix whose element ...
3
votes
4answers
383 views

Determinant of sum of Kronecker products

Given four real symmetric matrices $A,B \in \mathbb{R}^{n \times n}$ and $C,D \in \mathbb{R}^{m \times m}$, is there an efficient way to compute the determinant: $\det|A \otimes C + B \otimes D |$
0
votes
1answer
39 views

Large scale least squares of non symmetric and non square problems

Given a system like $b=Ax$ with an non symmetric and non square $A$ I would like to solve it having many elements in $x$ (lets say $10^7$). There is a large amount of algorithms for symmetric ...
1
vote
1answer
130 views

Decompositions of sparse symmetric matrices and methods for solving large linear equations

I am writing code for solving linear equations of the form $$A_{n\times n}\cdot x=1_n$$ where $n$ is on the order of $10^6$ and $A$ is a symmetric matrix with approx $10^3$ nonzero entries in each ...
4
votes
0answers
88 views

Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form: \begin{equation} A = \left[\begin{array}{c|c} ...
3
votes
2answers
139 views

QR-Decomposition of matrix valued function

Suppose I have a matrix valued function $$ F:\mathbb{R}\rightarrow\mathbb{R}^{m\times n},\qquad F(x)=\tilde Q\tilde R+xu_1v_1^T+xu_2v_2^T $$ where $\tilde Q\in\mathbb{R}^{m\times m}$ is orthogonal, ...
3
votes
1answer
132 views

submatrix of a given size with maximum frobenius norm

Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
-1
votes
1answer
94 views

Convergence for symmetric, positive semi-definite operator

Assume $u$ is a vector in the Euclidean space $\mathbb{R}^N$, $\|u\|=\sqrt{\langle u, u\rangle}$, where $\langle u, v\rangle = \sum_{i=1}^N u_i v_i$. I have that $\|u^{k+1}-u\|\leq \|I - c ...
0
votes
1answer
142 views

Perturbation of Cholesky decomposition for matrix inversion

I am looking for a computationally cheap way to compute $x$ such that $$(L L^T + \mu^2 I)x = y$$ where $L \in \mathbb{R}^{n \times n}$ is a lower triangular definite positive matrix (with some very ...
10
votes
2answers
388 views

Determinant and eigenvalues of a specific matrix

This came up in a conversation with an engineer friend of mine. Let $c>0$ be a constant. Let $A_{ij}$ be an $n$ by $n$ matrix with entries $$ A_{ij} = e^{-c(i-j)^2}. $$ Is there a name for this ...
1
vote
1answer
66 views

Augmenting orthonormal system into complete orthonormal system in a numerically stable way

Let us suppose we have a, say, 10 dimensional real space with 3 orthogonal unit vectors given. How do I complete this orthonormal system with 7 additional vectors into a complete ONS in a way that is ...
1
vote
0answers
73 views

How to solve a divergent linear system using iterative methods?

I have a matrix A which is symmetric and non-diagonal dominant. I tried to use Jacobi/Gauss-Seidel/SOR to solve it but it diverges. Is there any mechanism to condition the matrix for convergence using ...
2
votes
2answers
182 views

Probability for a random positive-semidefinite matrix to not be positive-definite?

If I take $A^TA$, where $A$ is a full-rank random matrix (let's say with Gaussian-distributed independent entries), can I expect it to be positive-definite? It will be positive semi-definite ...
5
votes
1answer
173 views

For a set of matrices $S$, find $X$ such that the elements of $SX$ commute

Let $S := \{A_0, A_1, \dots, A_d\}$, where $A_k \in \mathbb{C}^{n \times n}$, be a set of (generally noncommuting) matrices. I am interested in finding a nonsingular $X \in \mathbb{C}^{n \times n}$ ...
2
votes
1answer
108 views

Updating $LU$ decomposition after adding a sparse matrix

How many elements of $LU$ decomposition of a symmetric matrix change after adding a sparse symmetric matrix? Is it more efficient to recompute $LU$ decomposition after adding a sparse matrix comparing ...
1
vote
2answers
253 views

Eigenvalue computation using inverse iteration

I have a positive definite matrix $A$. I need to compute the max eigen value of $A$ using inverse iteration. The problem is that there are duplicate maximum eigen values and so inverse iteration ...
2
votes
0answers
159 views

What would be a better method for numerical diagonalization of a certain Vandermonde-like matrix?

For the fractional iteration of the $\exp()$-function Hellmuth Kneser had 1942 proposed an analytic solution valid on the real numbers; there is a technical implementation for Pari/GP of this method ...
1
vote
0answers
147 views

The rationale of QR algorithm for computing eigenvectors

For a symmetric matrix $A$, the rationale for the success of applying QR to compute the spectral decomposition of $A = UDU^T$ is, for large $k$, the QR factorization of $A^k = Q_kR_k$ obeys, ...
7
votes
1answer
768 views

efficient rank-two updates of an eigenvalue decomposition (or more genearlly SVD)

Let $A$ be a symmetric matrix with eigenvalue decomposition $UDU^T$. Golub, et al. and Bunch, et al. have shown that given such an $A$, the eigenvalue decomposition of $A+\rho xx^t$ may be computed ...
4
votes
0answers
133 views

Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D ...
0
votes
1answer
111 views

QR alogrithm for eigenvalue problem [closed]

Considering pure QR algorithm (without shifts and preliminary tridiagonal reduction) are there sufficient conditions for algorithm to converge to quasi-diagonal form? For the the following matrix $$ ...
5
votes
0answers
89 views

Inverses of the sums of all possible subsets of a set of symmetric and positive definite matrices

I have a set of $c$ matrices $A_1 ... A_c$ which are all symmetric and positive definite. I would like to calculate the inverses of all the possible sums, i.e. ...
3
votes
2answers
1k views

Sparse approximation of the inverse of a sparse matrix

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix? The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...
1
vote
2answers
233 views

Alternative to Choleski Decomposition for Correlation Matrix

Let $\Sigma$ be a correlation matrix, ie. symmetric. The Choleski decompositon gives upper triangular $A$ such that $A^TA = \Sigma$. Instead of upper triangularity, we are looking for $A$ that is not ...
6
votes
1answer
429 views

The singular values of the Hilbert matrix

The $n\times n$ Hilbert matrix $H$ is defined as $H_{ij} = \frac{1}{i+j-1}, \qquad 1\leq i,j\leq n$ What is known about the singular values $\sigma_1\geq\ldots\geq \sigma_n$ of $H$? For example, ...
4
votes
1answer
58 views

Algorithm to quickly compute the individual inverses of a linear sequence of matrices

Fix $n \times n$ real symmetric positive definite matrices $A$ and $B$. Fix vectors $x$ and $y$ in $\mathbf{R}^n$. I want to compute the following bilinear products quickly: $\{x^T (A+mB)^{-1} ...
2
votes
0answers
141 views

Error bound on matrix vector multiplication

I am multiplying a matrix $A$ with vector $p$. However, the matrix $A$ isn't accurate. Some (a very small fraction) of the element's value is changed from $a_{i,j}$ to {0,$-a_{i,j}$, $2a_{i,j}$}. ...
3
votes
1answer
77 views

Conjugate gradient algorithm where first search direction is not equal to residual

In usual formulation of conjugate gradient algorithm initial search direction is taken to be the residual (so residual and search direction spans Krylov subspace). However, in cases where inexact ...