Questions on the algorithmic/computational aspects of linear algebra, including the solution of linear systems, least squares problems, eigenproblems, and other such matters.

learn more… | top users | synonyms

3
votes
0answers
41 views

Does there exist a Fourier transform algorithm for perturbed data?

Assuming I have a length-$n$ real vector $x$ and have already computed its Fourier transform $\hat x$ (in time $O(n\log n)$), I would like to compute the Fourier transform of $y = x + \delta x$, where ...
0
votes
2answers
41 views

Angle of rotation at a point in a deformed triangle

I have a 2D triangle which deforms with each vertex moving by some small ($\sin(x) \approx \tan(x) \approx x$) displacement vector. The displacement of any point in the triangle is linearly ...
4
votes
0answers
24 views

Pseudoinverse of perturbed matrix

How does the pseudo inverse of a full column rank matrix change if I rescale a single row? In more detail the problem is the following: We have a fixed matrix $V$ with linear independent columns and ...
3
votes
1answer
63 views

Condition number of $X^{T}AX$

$A$ is a symmetric matrix and is known to be invertible. $X$ is rectangular of size $(N+p) \times N$ with $p > 0$ but full column rank. Can we provide an upper bound on the condition number of ...
0
votes
0answers
30 views

Constrained SVD/Lanczos given left/right matrices are banded

$A$ is a symmetric (known to be invertible) matrix of size $(N+p) \times (N+p)$ and $X$ is a rectangular matrix of size $(N+p) \times N$. The product $X^{T}AX$ is well-defined and non-singular. One ...
1
vote
0answers
46 views

Computing eigenvectors from the QR algorithm

I've seen a few other posts on this topic but none have full answers. I'm trying to implement some eigen-decomposition algorithms. I've managed to get the Explicit QR algorithm and the Implicit ...
0
votes
1answer
57 views

Extending the Frobenius inner product to all matrix inner products

So in ${\bf R}^{n\times p}$ we have the Frobenius inner product given by $$\langle A, B\rangle=\text{tr}(A^TB)$$ which can be interpreted as the Euclidean inner product on ${\bf R}^{np}$. My ...
0
votes
0answers
30 views

Unitary matrix representing Discrete Fourier Transform

Let $F_n\in\mathbb{C}^{n\times n}$ be the unitary matrix representing the discrete Fourier transform of length $n$ and so $F_n^{H}\in\mathbb{C}^{n\times n}$ is the inverse DFT of length $n$. For ...
2
votes
2answers
111 views

Are the Finite Difference and Finite Volume Methods different after the application of the Gauss Divergence theorem on the FVM?

I have a rudimentary question about the differences between finite difference (FDM) and finite volume methods (FVM). In FDM we concentrate on the nodes (points) in space while in FVM we concentrate ...
3
votes
1answer
97 views

What category is this problem?

My first question, please excuse me if its too basic. I have a matrix of evenly spaced geographical points; say 10 x 10, which I will call seed points. Each seed ...
1
vote
0answers
37 views

Reorder eigenvalues in QZ factorization in Python-Scipy /Matlab [closed]

Python and Scipy seem capable of replicating the QZ factorization of Matlab when the option "complex" is used in the command scipy.scipy.linalg.qz Yet, it seems that is still not possible to obtain ...
10
votes
1answer
225 views

Smallest eigenvalue without inverse

Suppose $A\in\mathbb{R}^{n\times n}$ is a symmetric, positive definite matrix. $A$ is big enough that it's expensive to solve $Ax=b$ directly. Is there an iterative algorithm for finding the ...
5
votes
1answer
64 views

Numerical computation of Perron-Frobenius eigenvector

I would like to efficiently and (to the extent possible) reliably find the Perron-Frobenius eigenvector of non-negative matrices. These are not stochastic matrices, they are typically dense, and their ...
3
votes
1answer
51 views

Calculating left eigenvector when I know the right eigenvector

I'm using power iteration to find the dominant right eigenvector of some large-ish matrices ($1000\times 1000$ to $10000\times 10000$ or so, maybe I'll need to go bigger later) with non-negative ...
6
votes
1answer
43 views

Finding all binary vectors with given A-length

I am given a $n \times n$ matrix $A$ with real entries and define the inner product $$\langle x,y\rangle = x^T A y.$$ I am also given an integer $k$ and need to find all binary vectors $x$ such that ...
5
votes
1answer
54 views

Code to update dense QR and Cholesky factorizations

I am looking for some production-ready code to update dense QR and/or Cholesky factorizations (by adding / removing rows and columns or making small-rank updates -- yes, I need all these cases). I ...
4
votes
2answers
88 views

Advice on handling many “small” matrices in parallel

I'm working on a small fun project on the side for a numerical method I've been working a bit with. Roughly, the computational problem I have to solve is the following: Assume you have a collection of ...
11
votes
2answers
163 views

Algebraic Multigrid: Why does the product of interpolation and restriction not result in something with norm 1?

I'm currently working with "A Multigrid Tutorial" by Briggs et al, Chapter 8. The construction of the interpolation operator is given as: Then construction of restriction operator and fine grid ...
2
votes
1answer
75 views

Templated Numerical Linear Algebra in Parallel

I have to invert large, but densely populated matrices with higher precision arithmetic. Therefore I am looking for something like the PLASMA library, which can do Cholesky or LU factorization in ...
2
votes
1answer
43 views

Sampling vector so they will have a given euclidean distances matrix

Given a matrix $M\in\mathbb{R}^{P\times P}$ , is it possible to sample $P$ vectors $u_i\in\mathbb{R}^N$, $i=1..P$ so that $\|u_i-u_j\|=M_{ij}$. Obviously for not any $M$ this is possible, i.e. it has ...
1
vote
1answer
74 views

Total Flop count for LAPACK DPOSV

I am looking at the LAPACK DPOSV routine that computes the solution to the real system of linear equations A * X = B. The routine description can be found here: ...
1
vote
1answer
51 views

How to compute the Jacobi matrix (tridiagonal matrix) of a polynomial with a recurrence relationship?

I am looking at Trefethen and Bau Exercise 37.1: I have two normalizations of the Legendre polynomials with corresponding recurrence relations: $$P_n(1)=1$$ which follows $$P_n(x) = \frac{2n-1}{n} x ...
7
votes
0answers
105 views

Fast computation of component-wise $\exp(-XY^T)G$ for random $G$

I have the following question: Suppose I have two matrices $X,Y$ both of size $m\times p$ and a random i.i.d Gaussian matrix $G$ of size $m \times k$, $m\gg p>k$. Is there a fast way to compute ...
4
votes
1answer
67 views

How to calculate log or exp of a value in GF(2^n) using log/exp table of GF((2^k)^m) where n=k*m?

Consider a $GF(2^n)$ field, a $GF(2^k)$ galois fields, where $n=k \times m$ and $GF(2^k)$ is a ground field of $GF(2^n)$. I’d appreciate pointers to papers or suggestions on: How to find $\log(a)$ ...
0
votes
2answers
51 views

Finding matrix form of Ellipsoid given general form

I have data that I would like to fit with an ellipsoid and I am currently fitting it via the following Matlab commands: ...
2
votes
1answer
57 views

Solving new linear system that comes from an $p$ enrichment

Let's say I am solving a simple Poisson problem using a Mixed (DG) finite element method. If we use orthogonal polynomials as basis functions we can write the finite-dimensional linear system as $$ ...
3
votes
2answers
121 views

Optimized parallel routine for $X' W X$ with $W$ diagonal

$X$ is a dense matrix of real doubles, typically of size 20 million rows and 500 columns, and $W$ is a diagonal matrix of real, non-negative doubles stored as a vector. I'm working in C and have ...
2
votes
0answers
50 views

Does Conjugate Residual really have convergence properties similar to that of Conjugate Gradient?

I have coded up a toy implementation of Conjugate Residual and have been testing it. Both wikipedia and the Saad claim that Conjugate Residual and Conjugate Gradient have similar convergence ...
2
votes
0answers
80 views

FLOPS of a linear system

I have two questions that I want to ask. Consider the following system: $$BM = A$$ i) $B$ is a $n$ by $n$ tridiagonal matrix and $A$ is a diagonal matrix. What is the leading order computation cost ...
5
votes
2answers
109 views

Does this partial eigen-expansion have a name?

This question is a follow-up to this one. Let $A\in \mathbb{R}^{n\times n}$ be large, sparse, symmetric and positive definite. Suppose for I already know $m<n$ eigenpairs of $A$, corresponding to ...
1
vote
0answers
41 views

Cholesky factorization of a block matrix

Let a Matrix $\mathbf{Y=[A\;b;b^T\;}d]$, where $d$ is a scalar, and $\mathbf{b}$ is a vector. How to find the cholesky factorization of $\mathbf{Y}$ if i know the cholesky factorization of ...
2
votes
1answer
67 views

Julia: ordschur command

I just started leaning Julia, and my command of it is still very preliminary. I am trying to reorder a Schur decomposition. In Matlab, I could use the ordqz command and just had to specify the ...
6
votes
0answers
66 views

What are some ideas to preprocess / precondition the following linear system?

Let $A\in \mathbb{R}^{n\times n}$ symmetric and positive semidefinite, and $\omega\in \mathbb{R}\setminus\{0\}$. I am interested in solving the following linear system for a range of values of ...
3
votes
1answer
71 views

Fast algorithm for computing matrix square root using randomized linear algebra?

Is there a fast algorithm for computing the matrix square root of a real symmetric matrix using random matrices or randomized algorithms?
6
votes
0answers
89 views

What strategies / decompositions would be useful to solve the following linear system repeatedly if I only care about time to solution?

Let $A\in \mathbb{R}^{n\times n}$ be symmetric positive semidefinite, and $B\in \mathbb{R}^{n\times n}$ be symmetric positive definite. Suppose $B$ is block diagonal so it is easy to invert. (We ...
4
votes
1answer
88 views

Obtaining column vectors of pseudo-inverse of a matrix

I need to compute the pseudo-inverse of a very large rectangular dense matrix without any special structure or properties. I run out of memory/computing power and have no access to a large parallel ...
9
votes
1answer
184 views

Iterative “solver” for $x^t \Sigma^{-1} x$

I can't imagine I'm the first to think about the following problem, so I'll be satisfied with a reference (but a complete, detailed answer is always appreciated): Say you have a symmetric positive ...
2
votes
1answer
95 views

Kernel of a Sparse Matrix

Given a sparse rectangular matrix $A$ (let's say, with dimension $n,m$ and number of non-zero elements $O(n)\sim O(m)$) with entries in $\mathbb Z/2\mathbb Z$ I'm looking for a basis of the kernel as ...
3
votes
1answer
107 views

GSL linear algebra LU/determinant precision

I am working with symmetric matrices of order $n \times n$ where $n \leq 50$. The diagonal elements of my matrices are a fixed number $d$ and the off diagonal elements are limited to two small numbers ...
4
votes
1answer
110 views

What factors are relevant when deciding between GMRES and schur complement solves?

Suppose I have a linear system $$ \left\lbrack \begin{array}{cc} M_1& S\\ S^{\mathrm{T}}& M_2 \end{array} \right\rbrack \left\lbrack \begin{array}{c} X\\ Y\end{array} \right\rbrack= ...
3
votes
1answer
56 views

Does $\log(\det(A))$ equals sum of log of diagonal elements of D in LDLT decomposition?

For a large matrix $A$, I need to evaluate the $\log(\det(A))$. I already have it's LDLT decomposition. Is it possible to evaluate the $\log\det$ with the elements of the diagonal $D$ of the LDLT ...
4
votes
1answer
59 views

Trust region - Newton: how to choose constants that determine trust region bound

In a trust region based Newton method, a number of constants are given as inputs to the algorithm that determine the updating rules for the trust region bound. Are these constants chosen arbitrarily ...
5
votes
1answer
188 views

What is a good way to solve the following linear system? (repeatedly)

Let $n,m\in \mathbb{N}$ be such that $m\ge n$. Let $M_1\in \mathbb{R}^{n\times n}$, $\{M_{2},M_{3} \} \subset \mathbb{R}^{m\times m}$ be symmetric positive definite and computationally cheap to ...
2
votes
0answers
46 views

Find constrained vectors maximizing angles between them - methods?

This is related to a question I had asked earlier, with the distinction that earlier I did not have a non-linear objective functional to minimize. The problem is reproduced below with added ...
2
votes
0answers
46 views

Symmetric nonnegative matrix factorization

Suppose $A\in\mathbb{R}_+^{n\times n}$ is symmetric. I would like to factorize $A\approx UU^\top$ by solving $$ \begin{array}{rl} \min_U & \sum_{ij} ...
2
votes
1answer
63 views

Parameter reduction algorithm for least square model

Question I am performing least squares fitting using an objective function of the form $f(\mathbf{x})$ where $\mathbf{x}$ is a vector of parameters containing around 20 elements. The model function ...
1
vote
2answers
138 views

QR decomposition

I have a matrix which is "almost" like an upper triangular just that the last row has non zero elements. And I want to perform the QR decomposition on that matrix. Does anyone know the "name" of such ...
0
votes
1answer
84 views

solver linear system equation

I need to solve to solve a "large" symmetric sparse linear systems, with matrix size 8000? I heard about HSL, ITPACK, but I don't know how to use them, and I am working in C language.
2
votes
2answers
118 views

Generation of random Matrix with Real eigen values

does anyone know any matlab algorithm that can help me generate a random matrix with REAL EIGEN values? Thanks.
1
vote
1answer
83 views

Max size of set linear equations to solve? (X=AX+B)

This question has also been asked at Stack Overflow. This is a very general question regarding the maximum size of a set of linear equations to be solved by today's fastest hardware, in the form: ...