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

5
votes
0answers
35 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
25 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
51 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
93 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
36 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
43 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
47 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
44 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
37 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
94 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 ...
8
votes
1answer
207 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
0answers
41 views

Iteration methods for solving rectangular or singular linear system of equations

I want to solve consistent system of linear equations $Ax = b$, where matrix $A$ is rectangular or singular square matrix. I am interested to know what are the available iteration methods to solve ...
1
vote
1answer
78 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
90 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
59 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
153 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
187 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
58 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
75 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
64 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
105 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
53 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
154 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} ...
3
votes
2answers
106 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
127 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
97 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
87 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
122 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
68 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
163 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
61 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
65 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
71 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
41 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 ...
2
votes
2answers
302 views

Eigenvectors: MATLAB vs LAPACK DGGEV or DGGEVX

If we call LAPACK DGGEV or DGGEVX routines for two badly-conditioned matrices in a C++ code, will we get the same eigen-values ...
3
votes
1answer
342 views

Why is my MATLAB code for back-substitution slower than the backslash operator?

I wrote the code below to invert an upper triangular matrix, avoiding any possible multiplication/subtraction by zero. It just uses $\frac{1}{6}n^3+\ldots$ flops instead of $n^3+\ldots$ flops. ...
2
votes
3answers
132 views

Is it better to do normalization after all orthogonalization in Gram-Schmidt process?

In Gram-Schmidt process, is it better to do normalization after orthogonalization of all the vectors in a basis, or to normalize each new vector immediately after it is created, from computational ...
5
votes
1answer
93 views

Solving Generalization of Saddle point problem

I am interested in knowing if there is a generalization of the Uzawa iteration for the linear problems of the form $$\left[ \begin{array}{ccc}A& B^T&0\\ B&0&C^T\\ 0&C&0 ...
0
votes
1answer
91 views

Diagonalize a circulant-plus-rank-one matrix

Suppose $A=uv^T$ where $u$ and $v$ are non-zero column vectors in $\mathbb{R}^n, n\geq 3$. $\lambda=0$ is an eigenvalue of $A$ since $A$ is not of full rank. $\lambda=v^Tu$ is also an eigenvalue of ...
1
vote
1answer
100 views

writing linear system in matrix form

I have the following set of linear equations $$a_{m+1,n}+a_{m-1,n}+m(a_{m,n+1}+a_{m,n-1})+(m^{2}+n^{2})a_{m,n}=f_{m,n}$$ Here $m$ and $n$ run from 1 to $N$, so there are $N^2$ equations for the ...
3
votes
1answer
130 views

Get symmetric Finite Difference matrix in non Laplacian settings

I would like to solve a system of differential equations $u+\nabla(\nabla\cdot u)=f$ or in more detail $a+\partial_t^2a+\partial_t\partial_xb+\partial_t\partial_yc=f$ ...
5
votes
1answer
150 views

Least-squares for a diagonal matrix

This is a follow-up to a different question I asked with more detail. For $v\in\mathbb{R}^n$, denote $D_v\in\mathbb{R}^n$ as the diagonal matrix with elements in $v$. Given a "tall" matrix ...
3
votes
3answers
157 views

Large overdetermined system of linear equations

I'm looking for a method to solve a large overdetermined system of linear equations in a least squares sense. The matrix is dense. I'd like to use a method that works even with limited memory (we ...
4
votes
2answers
103 views

Solving “Hadamard systems”

Suppose we have two matrices $A$ and $B$ (we can assume they're symmetric; if absolutely necessary I think they may be positive definite). Then, is there any technique for solving $$(A\circ B)x=b,$$ ...
0
votes
2answers
89 views

How to determine the number of c points in algebraic multi grid

I am trying to write an algebraic multi-grid solver (in c++). At a given level I determine which nodes are c-points and which nodes are f-points (where the total number of c and f points equals the ...
2
votes
0answers
73 views

Does it matter if I use principal component analysis on the transpose instead of the original matrix?

My data set is a 60x10 matrix. I performed principal component analysis of this matrix with matlab using the princomp(AdjustedData) after I adjusting my original data set by subtracting the mean of ...