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

1
vote
1answer
40 views

On the flight/matrix free SVD of large sparse matrix

I am trying to apply SVD to large sparse matrices. I already compared the performances of Propack and irlba to those of the matlab svd and svds. These two packages enhance significantly the computing ...
2
votes
0answers
49 views

preconditioned Uzawa method with Petsc

I am trying to improve the resolution of a Stokes problem (P2/P1 on unstructured mesh) defined by the matrix $M$: $M= \begin{pmatrix} A_u & 0 & B_u \\ 0 & A_v & B_v\\ B_u^T & ...
2
votes
0answers
31 views

Hessian eigenvalues in 4D-VAR data assimilation

I am using variational data assimilation (4D-VAR) to estimate emissions of anthropogenic greenhouse gases using a rather complex atmospheric transport model. Hence, the optimal solution to my problem ...
5
votes
3answers
71 views

Does the Lanczos starting vector have to be random?

In all descriptions of the Lanczos vector, it's said that the starting vector is random. But let's say I'm only interested in the eigenvector associated with the lowest eigenvalue (as is the case ...
1
vote
0answers
32 views

Optimization with matrix exponential constraint

Suppose I'm optimizing for an unknown $x\in\mathbb{R}^k.$ I have a linear operator $A(\cdot)$ that maps $x$ to an $n\times n$ symmetric matrix, i.e., $A:\mathbb{R}^k\rightarrow\mathbb{R}^{n\times ...
4
votes
1answer
119 views

Appropriate iterative linear solver for an eigenvalue problem

I'm trying to solve a generalized eigenvalue problem $$Ax = \lambda Bx, \quad A = A^\top > 0,\; B = B^\top > 0$$ with $\lambda \approx \sigma$ using Rayleigh Quotient Iteration (RQI) (RQI is ...
4
votes
2answers
91 views

Under what circumstances can two (nearly) identical sparse matrices give different solutions to Mx = b?

Suppose I have two sparse matrices, $A$ and $B$, of size $N \times N$. They each have the same sparcity pattern ("footprint"). They each also have values which in theory should be identical, but ...
0
votes
0answers
93 views

How to compute this double integral?

Let $$T=1, K=100, S_0=100, \sigma=0.05, r=0.15. $$ Define $\nu:=\frac{2r}{\sigma^2}-1$ and $$H(y,z)=\frac{z e^{\pi^2 /4y}}{\pi \sqrt{\pi y}}\int_0^{\infty} e^{-z \cosh(u) -u^2/(4y)} \sinh(u) ...
1
vote
1answer
52 views

Kronecker products and basis contractions (ie. B.A.Transpose[B]) in C?

I have implemented a basis transformation in C of the following form kron[A,A]*B*Transpose[kron[A,A]] where A and ...
0
votes
0answers
51 views

C++ Library: What is the Most Efficient Library that Factorizes a Polynomial?

I need to know what library is the fastest one that can factorize a polynomial of large degree whose coefficients are big integers. I have tried NTL library to factorize a monic polynomial but it is ...
8
votes
0answers
139 views

scale invariance for line-search and trust region algorithms

In Nocedal & Wright's book on Numerical Optimization, there is a statement in section 2.2 (page 27), "Generally speaking, it is easier to preserve scale invariance for line search algorithms than ...
3
votes
0answers
51 views

What is the source of the error in the Sherman-Morrison formula application?

The Sherman-Morrison formula $$ (A+uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u} $$ results in small errors in relation to the standard matrix inverse operation after each application, ...
3
votes
1answer
149 views

Alternatives to numpy.einsum

Given an $n_1 \times \cdots \times n_k \times g \times g$ tensor $A$ (i.e. a collection of $g \times g$ matrices) and an $n_1 \times \cdots \times n_k \times g$ tensor $b$ (i.e. a collection of ...
3
votes
1answer
162 views

Finite Difference Beam Propagation Method problem

I am trying to implement the finite difference beam propagation method to study the propagation of a TE light signal through a waveguide. However, my solutions are exponentially growing, and display ...
3
votes
1answer
95 views

How to calculate $det(X^TX)$ efficiently, update one column of X each time

$X_{1} = (A, b)$, where $X_{1}$ is a $n\times p$ matrix, $A$ is a $n\times (p-1)$ and $b$ is $n\times1$. First calculate $\det(X_{1}^T X_{1})$, then update $b$ with $c$, st. $X_{2} = (A, c)$ and ...
2
votes
1answer
76 views

Recommendation for C/C++ library which offers Schur complement functions?

I need to find C/C++ libraries which offer function for computing Schur complement. I know about MUMPS and Pastix, but I need more of them to compare them in my research. Do you have any experience ...
2
votes
2answers
113 views

C++ Library: What is the common libraries that do polynomial arithmetic?

I need to know what libraries (in C++) support polynomial arithmetic specially over a field. So I can give to it an array of coefficients of polynomial over a field and it returns the roots of ...
2
votes
0answers
82 views

C++: How to find the roots of polynomial modulus N [duplicate]

I need to know what library, given a vector of coefficients and modulus N return the roots of polynomial modulus N. The library should support big integer. I'm coding in C++.
2
votes
2answers
94 views

SVD of large block-hankel matrix

I am trying to do SVD of a large block-hankel matrix for model order reduction (Low rank approximation). However, I quickly run into memory issues in forming the large Block-Hankel matrix and CPU ...
5
votes
1answer
163 views

Solving Linear Systems in Julia

To give you some context, I am currently implementing a simple finite element solver in Julia. I am getting run-times that are 70% of a Matlab code. (Both codes are essential equivalent in ...
1
vote
1answer
67 views

Fast algorithms for computing only the generalized singular values (but not the vectors)

I am interested in computing only the generalized singular values, and was wondering if this was faster (and by how much?) than computing the full GSVD. In particular, I was wondering what the ...
1
vote
0answers
79 views

Sparse Linear Algebra vs Dense Linear Algebra

I am interested in a reference in the literature that discusses the performance of Dense Linear Algebra (blas routines) and dense linear algebra (sparse blas routines). I am interested in knowing for ...
2
votes
2answers
144 views

BLAS, LAPACK or ATLAS for Matrix Multiplication in C

I am trying to find the most optimized way to perform Matrix Multiplication of very large sizes in C language and under Windows 7 or Ubuntu 14.04. And searching led me to BLAS, LAPACK and ATLAS. ...
2
votes
1answer
112 views

Solve $AX = B$ where $X^T X = C$

Is there a natural way to find the solution to $$AX = B, X^TX = C \enspace \text{?}$$ $X$ is a matrix and has a small number of rows, and $A$ is sparse. An approximate solution would be fine.
3
votes
1answer
85 views

Trust-region Newton: implementation issue with Conjugate Gradient calculations

UPDATE: The problem turned out to be the step (refer penultimate paragraph below) where I was factoring out a small value from the vectors of the numerator and denominator and then computed dot ...
1
vote
1answer
95 views

How to make this matrix efficiently?

Originally posted on stats.stackexchange, I'll pair the post down to something a bit more general. Suppose I have vectors $\{\mathbf{\delta}, \mathbf{x}_1, \ldots, \mathbf{x}_J\}$, where $\delta \in ...
3
votes
1answer
83 views

Givens-Rotation from the Right Side (used in QZ-Algorithm)

i need to get a Givens-Rotation, which zeros a matrix entry when multiplied from the right side. I did already look at this Topic ...
2
votes
1answer
69 views

How do I make sparse solvers to accept custom matvec function insted of matrix?

I have tried it with Lis, Intel mkl and PETSc. Everywhere you need to pass an actual matrix ...
9
votes
1answer
117 views

What iterative method can effectively solve a linear system with this kind of spectrum

I have a linear system with matrix which eigenvalues are uniformly distributed on the unit circle like this: Is it possible to solve this kind of system effectively by iterative method, maybe with ...
1
vote
1answer
54 views

Constrained linear least squares matrix equation

It has been a while since I have done linear least squares, so forgive the simple question, but here goes: I am attempting to find the best fit coefficients, $\{c_i\}$, of a linear combination of ...
6
votes
1answer
142 views

How is Krylov-accelerated Multigrid (using MG as a preconditioner) motivated?

Multigrid (MG) may be used to solve a linear system $Ax=b$ by constructing an initial guess $x_0$ and repeating the following for $i=0,1..$ until convergence: Compute the residual $r_i = b-Ax_i$ ...
2
votes
0answers
38 views

Rank deficient Jacobian in discretized periodic solutions to autonomous ODE

I'm trying to numerically find periodic solutions to different systems of autonomous nonlinear ordinary differential equations. I decided to use a finite difference scheme and solve the resulting ...
6
votes
3answers
265 views

Algorithm for solving Ax = b with unknown A and x

I would like to solve for the optimum $A$ values for a series of matrix equations $Ax_{1} = b_{1}, Ax_{2} = b_{2} ... Ax_{n} = b_{n}$ where only the $x$ values are known and when I start with an ...
1
vote
0answers
39 views

Elemental vs DPLASMA

I want to use one of these two libraries into my C++ project to basically invert a dense matrix (with Cholesky). Of course, I am interested in a distributed environment. Both libraries seem nice so ...
2
votes
1answer
95 views

Hessian-free and Truncated Newton methods

In this paper on Deep Learning for Machine Learning, the approach is referred to as Hessian-free method. That is because the Hessian is never computed explicitly. Instead, the product of the Hessian ...
5
votes
0answers
58 views

How does an unpivoted QR fail to reveal rank?

An unpivoted QR factorization produces a triangular factor $R$. A rank-revealing QR factorization is typically done with column pivoting. My question is, how does an unpivoted QR factorization fail to ...
0
votes
0answers
28 views

Locally evaluate nonlinear dynamic system's stability using eigenvalues

I'm working with Computational Neuroscience. I have a large Synaptic Matrix (x axis: presynaptic NeuronID, y axis: postsynaptic NeuronID) in a Modular network. This matrix is close to a random one and ...
0
votes
0answers
61 views

How to curve fit an unknown function?

I have data which can be described by $y=f(x,z)$ where $z$ varies from 170 ~ 154. Now values given by $ks$ are known sample values that equals value given in the table header, $uks$ are unknown ...
2
votes
0answers
102 views

Help understanding the so-called “spectral method”

This is a follow-up question to an answer I read here. $M$ is some hermitian matrix and $V$ an vector. Since the matrix is hermitian, you could use it as a hamiltonian to propagate it in ...
4
votes
1answer
49 views

Estimating the local compression/expansion ratio for a transformation on a point cloud

Let's say we have an unorganized point cloud P1 with N points, each with coordinates {x,y,z}. We apply non-rigid transformation to P1 (translation + rotation + warping), to obtain point cloud P2. ...
0
votes
0answers
15 views

Improvement of Minimum description length (MDL) estimate

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
1answer
53 views

Best path for estimation

I have a Cartesian grid (100x100) in which some of the points are known (30 out of 10,000) and the rest are unknown. I want to use the known points and estimate the other cells. Is there any ...
0
votes
1answer
100 views

Armadillo eig_sym() for extracting eigenvalues. Is it parallel at all? [closed]

After wasting 3 days with scalapack, I gave up and moved to Armadillo, considering it uses lapack underneath its beatiful and easy interface. I would like to calculate the eigen values and eigen ...
0
votes
1answer
54 views

how to partition a graph(matrix) into subdomains with different sizes

i am studying the solver for PageRank problems which drived from the web link graph. I have tried using METIS to divided the matrix into subdomains, but METIS can only produce subdomains with nearly ...
0
votes
0answers
31 views

How to compute the inner system(like schur complement) effeciently

i got a factorization of $A$ like $A=D+F*H$, where $D$ is a block diagonal matrix and $F,H$ are low-rank matrices. I consider to use the Woodbury formula to construct a solver: ...
1
vote
0answers
45 views

Using Centroid decomposition instead of SVD

This paper says centroid decomposition (CD) is an approximation to singular value decomposition (SVD). First I do not understand CD yet, since code is available I just want to try it out how it works ...
1
vote
2answers
222 views

Incremental SVD implementation in MATLAB

Is there any library/toolbox which has implementation of incremental SVD in MATLAB. I have implemented this paper, it is fast but does not work well. I tried this but in this also error propagates ...
10
votes
1answer
422 views

Danger of complex arithmetics in scientific computing

The complex inner product $\langle u,v\rangle$ has two different definitions decided by conventions: $\bar{u}^Tv$ or $u^T\bar{v}$. In BLAS, I found the routines cdotu, zdotu, and cdotc, zdotc. The ...
1
vote
1answer
375 views

eigenvalues of a general complex matrix in C++

Is there a free C or C++ library including a routine for the eigenvalues of a general complex matrix? I checked a number of linear algebra packages like Eigen, but there does not seem to be support ...
5
votes
1answer
129 views

Caveats of Hessian free method

Hessian free iterative optimization techniques like Newton-CG, do not explicitly compute the Hessian but instead approximate the product of the Hessian with a vector through finite difference. The ...