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

2
votes
1answer
55 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
81 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
73 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
90 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 ...
2
votes
1answer
49 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
62 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
114 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
48 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
130 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
35 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
247 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 ...
0
votes
0answers
36 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
62 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
55 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
27 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
56 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
96 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
44 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
14 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
69 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
50 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
39 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
152 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 ...
9
votes
1answer
336 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
157 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
101 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 ...
0
votes
0answers
60 views

Sparse MatrixExp acting on a vector

I am looking for a library implemented in C++ which would be able to compute action of matrix exp on a vector $$w = e^{A}v$$ I want to operate on sparse matrices with complex entries, not on real ...
3
votes
2answers
163 views

Which software packages can solve linear systems that are not stored

I have matrices that are extremely easy to compute pointwise, but are too large to store. (they are not sparse) On the MATLAB site I was told MATLAB doesnt support computations with non-stored ...
8
votes
2answers
204 views

Does the matrix condition number affect accuracy of iterative linear solvers?

I have a rather specific question regarding the condition number. I run FEM simulations which have multiple length scales to them which results in a huge disparity between the largest entries and the ...
1
vote
1answer
59 views

Sparse linear system of certain type

Let $n_1,n_2 \in \mathbb{N}$ and $n=n_1n_2$ and $b\in \mathbb{R}^n$. I have a SPD-matrix $A=(a_{i,j})\in \mathbb{R}^{n \times n}$ with $a_{i,j}=0$ if $|i-j| \notin \{0,1,n_1\}$. Can we solve the ...
0
votes
0answers
91 views

Advantages and Disadvantages of PETSC vs HyPre?

What are some of the differences between using Petsc and using Hypre? Also what are some of the advantages and disadvantages of both? Does Petsc use more memory or run faster? Thank you very much for ...
3
votes
1answer
70 views

Derivative of a generalized eigenvalue problem

I want to compute the derivative of a generalized eigenvalue $\lambda$ which is solution of $A u = \lambda Bu$ ($A,B,u,\lambda$ all depend on $t$; in my case $A,B$ are known explicitly, and the ...
0
votes
1answer
113 views

Doubt regarding stopping criterion for Newton method

I am solving an unconstrained convex optimization problem, which can easily have a million variables. I am trying to get a working system with a toy problem of around 200 variables. I am noticing that ...
1
vote
0answers
55 views

Block preconditioners and condition number

I am working with block Jacobi like preconditioners which are very cheap for my problem. But I could not find much about the dynamics of basic preconditioners (block Jacobi, Gauss-Seidel, ILU etc). ...
0
votes
2answers
164 views

How to obtain a convergent solution iteratively for a linear system of equations? [closed]

I am working on a problem that requires an iterative procedure to solve a linear system of equations, the system of equations in matrix form is: $$\underbrace{\begin{bmatrix} r_{11} & r_{12} ...
5
votes
2answers
180 views

Why do structured and unstructured discretizations give different errors?

It is necessary for me to solve a Poisson problem with a numerical method on a square domain with two types of triangular mesh: uniform triangular mesh (using uniform distribution nodes on square) and ...
3
votes
2answers
141 views

Well-posedness of a linear elasticity problem and Navier-Cauchy equation

I read a master thesis on a topic I'm interested too. This work concern the solution of the displacement equation of motion for a homogeneous, elastic, isotropic material: $$\rho \ddot{\mathbf{u}} - ...
0
votes
0answers
102 views

Estimating the second largest eigenvalue

I am currently dealing with the following problem. I am given a matrix $A$ of order $n \times n$ where $n \leq 20.$ The principal $(n-1) \times (n-1)$ matrix of $A$ is symmetric and contains only ...
0
votes
1answer
39 views

compute change of phase along closed contour

The following image represents the phase of a wavefunction (in radians) on a square lattice, where $m$ and $n$ label the lattice sites. Computationally speaking, it is the density plot of a 41x41 real ...
1
vote
0answers
47 views

Library for calculating determinants with Kronecker products

I need to calculate a determinant consisting of vectors, using the Kronecker product as product. As an example I would need to be able to calculate: $\left| \begin{array}{cc} ...
2
votes
0answers
94 views

Using SVD to biorthogonalize left and right eigenvectors?

I have a set of left and right eigenvectors from an nonsymmetric eigenproblem, and I'd like to biorthogonalize them. I tried Gram-Schmidt, but this fails for most cases. I then read that the SVD is ...
1
vote
0answers
146 views

eigs routine in octave

I am using octave and observed a problem with the eigs-routine for non symmetric matrices. Using GNU octave version 3.8.1 the code below gives significant difference of eigenvalues although same ...
1
vote
0answers
75 views

Search Direction in Conjugate Gradient

Could you help me with a Conjugate Gradient question? In using CG to solve Ax=b, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous direction ...
1
vote
1answer
166 views

Solve for a matrix given two vectors

I'm programming a beam finite element model by following a book (Nonlinear Finite Element Analysis of Solids and Structures Volume 2, in case you're wondering!). I've come across the following ...
2
votes
0answers
65 views

Algorithm code for Drazin and Bott-Duffin inverse (Matlab or C)

I could find the common Moore-Penrose algorithm, but I couldn't find the Drazin or the Bott-Duffin generalised inverse, except for some very specific cases, useless for my studying purposes. Is there ...
5
votes
0answers
72 views

Find the solution of linear equation using Wiedemann/ Krylov method

Let given $M =$ 1 0 1 0 1 1 1 1 1 and $b =$ 1 0 1 How to find the solution $x_3$ where ...
1
vote
1answer
73 views

Numerical eigenbasis for a unitary matrix

Do you know what numerical software computes an eigenvector basis for a unitary matrix? Say I have a unitary matrix $U$. If its eigenvalues are simple (no multiplicities), then for instance Matlab ...
2
votes
0answers
46 views

In-place QR update: deleting a column

Background I'm trying to do an update to a "thin" QR decomposition ($A = QR$, where $Q$ is $\mathbf{R}^{m,n}$, the first few columns (up to the matrix rank) of an orthogonal matrix and $R$ is upper ...