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

0
votes
2answers
74 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
64 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 ...
3
votes
2answers
60 views

Schur(QZ) Decomposition Differences

I am having issues understanding why different languages are producing different answers for the Schur(QZ) decomposition. I am working on writing some old stuff from Matlab into Julia and Python and ...
1
vote
0answers
19 views

linear solution of curve fitting on multiple linear functions differing by a multiplier

I am facing the following problem. I know nonlinear least squares can provide a solution but I am wondering if a linear way to solve this data fitting problem may exists. This is my input dataset: ...
1
vote
1answer
83 views

What is the algorithm that matlab used in its built-in function 'pca'?

Do anyone know what is the algorithm that MATLAB used in its built-in function "pca"? I have the following data set: 148.9820 55.8438 210.2150 149.3030 56.8891 208.4280 151.4400 ...
3
votes
1answer
123 views

Parallel Gram-Schmidt algorithms

I've heard that classical Gram-Schmidt is more amenable to parallelization than modified Gram-Schmidt; apparently the reason has something to do with "level 2 BLAS", which I'm not familiar with. ...
0
votes
1answer
55 views

Translate a 3D point along a heading

I need to translate a point (P1) in 3D a certain amount, call it stepSize, along a vector described by a heading composed of ...
0
votes
0answers
52 views

LU Factorization update when adding columns

I am looking for a way to update the LU factorization of a general $m \times n$ matrix after adding a column to the matrix. I have to iterate this procedure so I will begin with a matrix that is $m ...
0
votes
0answers
21 views

Updating the LU Factorization [duplicate]

I am looking for a way to update the LU factorization of a general m×n matrix after adding a column to the matrix. I have to iterate this procedure so I will begin with a matrix that is m×1 and go all ...
3
votes
1answer
57 views

Dimensionality reduction of the domain of f(x)

I'm wondering if there is something analogous to a PCA for data sets where there is a dependent variable. (Though I am interested in any method of dimensionality reduction, PCA is just an example.) ...
0
votes
0answers
44 views

Principal Components Analysis Not Behaving as I Expect it to

I have a bunch of points in $\mathbb{R}^3$ that I would like to translate and rotate so that their center is at the origin and the variance along the $x$ and $y$ axes are maximal (greedy, and in that ...
6
votes
1answer
92 views

Efficient RQ decomposition

I have an upper trapezoidal matrix stored in column major format. That is, my matrix looks like this: I'd like to RQ decompose it, and store Q in the rectangular part of my upper trapezoidal ...
2
votes
1answer
143 views

Comparing Eigenvectors, Mathematica vs. Matlab

I am trying to create the same out puts in Mathmatica and Matlab, however I am running into trouble aligning the eigenvectors with the eigenvalues, I think the Matlab is doing something slighly more ...
1
vote
3answers
76 views

rank-deficient NNLS

I want to find the minimum-norm solution to a rank-deficient least-squares problem, subject to positivity constraints, e.g. $$\min_x\ \|x\|^2 \quad s.t.\quad Ax = b,\ x \geq 0$$ where $A$ is large, ...
3
votes
1answer
91 views

How does matrix-matrix product scale with multiple CPUs?

These days, one can have 64 cores in a single node. I wonder how well the dense matrix-matrix product (SGEMM and DGEMM) scales ...
1
vote
1answer
58 views

Symbolic Computations with Block Matrices in Maple

Due to the derivation of an algorithm I tried to use Maple (9.5) to calculate some block matrix expression. Unfortunately Maple seems to ignore the assumption I set on the variable. Lets consider the ...
5
votes
2answers
219 views

Recommendations for symmetric preconditioner

Given symmetric, positive-definite matrix $A$ and its preconditioner $M^{-1}$. What's kind of preconditioner $M^{-1}$ which preserve the symmetry of $M^{-1}A$?
3
votes
1answer
63 views

State-of-the-art for active set optimization algorithms?

Given a problem like this: $$ \text{min } ||Ex-f|| \text{ s.t.}$$ $$ Gx \ge 0$$ $$ Cx = d $$ And assuming that the matrices are medium sized (dimensions in the low thousands) and dense, what's the ...
0
votes
0answers
41 views

Lapack : dgeev strange behaviour

I have a problem that is quite strange. I use c++ and dgeev Lapack to diagonalize and find the eigenvectors of a 36x36 real non symmetrical matrix. The documentation explains the following : if ...
5
votes
2answers
77 views

Sparse smallest eigenvalue problem on a linear subspace?

I am interested in methods for solving the optimization problem $$ \begin{array}{rl} \arg\min_x & x^T A x \\ \mathrm{s.t.} & x^T x = 1 \\ & Bx = 0 \end{array} $$ where $A$ is symmetric ...
7
votes
1answer
67 views

Do C++ matrix libraries translate compound vector operations to single loops?

I am trying to replicate Fortran90 array syntax using a C++ library. The libraries themselves are discussed at length in this question. They can all do something like this: ...
1
vote
1answer
56 views

Conditioning of matrix factorizations and square roots

For my application, I need factors $\tilde C$ so that $$ \tilde C{}^T \tilde C = C^TMC $$ where $C$ is a long matrix, i.e. $C$ has much more columns than rows, and $M$ is a small symmetric positive ...
5
votes
1answer
157 views

Testing if a matrix is positive semi-definite

I have a list ${\cal L}$ of symmetric matrices that I need to check for positive semi-definiteness (i.e their eigenvalues are non-negative.) The comment above implies that one could do it by ...
7
votes
1answer
125 views

Algorithm to calculate the exponential of an Hessenberg matrix

I am interested in computing the solution of a lage system of ODEs using a krylov method as in [1]. Such method involve functions related to the exponential (the so-called $\varphi$-functions). It ...
0
votes
1answer
89 views

solving underdetermined system of equations with a sparse matrix as input

I am using Matlab to solve Ax=b and my A is very large, sparse, binary and also rectangular. I saw the Matlab backlash \ operator help and it states that if A is rectangular then it will use the QR ...
3
votes
1answer
75 views

Threaded QR with column pivoting

My program needs to perform pivoted QR decomposition on tall (e.g. 1e9 by 100) matrices. I run into the bottleneck that the major computational time of my program is spent on doing serial pivoted-QR ...
4
votes
2answers
113 views

Spectral decomposition of symmetric matrix

What is a good direct method to compute the spectral decomposition / Schur decomposition / singular decomposition of a symmetric matrix? "Direct" means as in LU decomposition, Cholesky decomposition, ...
15
votes
5answers
522 views

20% performance penalty for a nice software design

I'm writing a small library for sparse matrix computations as a way to teach myself to make the best use of object-oriented programming. I've worked really hard on having a nice object model, where ...
0
votes
1answer
98 views

Flop counts for LAPACK symmetric eigenvalue routines DSYEV, DSYEVD, DSYEVX and DSYEVR

LAPACK has following 4 routines for calculating eigenvalues of a real symmetric matrix; namely DSYEV, DSYEVD, DSYEVX and DSYEVR (DSYEVR being the recommended one). If I were to calculate both ...
1
vote
2answers
62 views

Performance metrics to compare initial-boundary value problem solutions

I am comparing the performance several finite difference methods of solving an initial-boundary value problem. There are several dimensions to this comparison: Number of cells Number of timesteps ...
2
votes
3answers
247 views

Eigenvalues of a sparse banded nonsymmetric matrix from an elliptic operator

I have a sparse matrix coming from the discretization of a 3D elliptic PDE. The matrix is banded with seven non-zeros diagonals. The sparsity pattern of the matrix looks like this (the actual matrix ...
3
votes
3answers
303 views

Fast vector - “diagonal” matrix multiplication

Let $\mathbf{1}\in\mathbb{R}^d$ be a vector with all elements equal to $1$. Define: $$\mathbf{D} = \mathrm{diag}(\mathbf{1}^\top,\mathbf{1}^\top,\ldots,\mathbf{1}^\top) = \begin{bmatrix} 1 \cdots 1 ...
3
votes
2answers
155 views

Solving linear system with 6 equations and 22 unknowns for six of the unknowns

I am trying to find the solution for the M variables in the following system. \begin{equation} 0 = C_{b} M^{b}_{x} - M^{a}_{x} k_{2a} + M^{a}_{y} \left(\omega - \omega_{a}\right)\\ 0 = C_{a} ...
11
votes
2answers
222 views

preconditioning a krylov method with another krylov method

In method like gmres or bicgstab it could be attractive to use another krylov method as a preconditioner. After all they are easy to implement in a matrix-free way and in a parallel environment. For ...
5
votes
1answer
145 views

Matrix completion algorithm

I am trying to implement the algorithm presented in this paper which tries to recover a matrix that represent a less noisier dataset of the intensities of the pixels of a set of images. In this case ...
3
votes
1answer
93 views

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

I asked the same question on mo.se and it was suggested that scicomp would be a better forum for it. So here it is: I am writing code for solving linear equations of the form $$A_{n\times n}\cdot ...
2
votes
3answers
89 views

importing PARI libraries ( in C++) with Python

I noticed that Python does not have a good datatype for rational numbers, certainly not for algebraic numbers like $\tfrac{1 + \sqrt{2}}{3}$ or the real root of $x^3 - 5x + 7$. They have the ...
0
votes
0answers
45 views

3D surface reconstruction

I've been studying about Photometric Stereo to reconstruct a 3D surface from images but I'm kinda lost in the part of the Depth Map. I understand that the normal vector should be orthogonal to the ...
1
vote
0answers
46 views

Implementing the transition matrix for page rank

I'm trying to implement PageRank. I'm reading the description here: http://nlp.stanford.edu/IR-book/html/htmledition/markov-chains-1.html Everything is very clear to me, however I'm concerned about ...
1
vote
0answers
53 views

An efficient way to convert between MKL and Armadillo types

We use Armadillo a lot in our code but there are places where we prefer to use MKL directly from Vector Math Library. We have cx_vec i.e. vector of doubles. But the exp function of armadillo uses ...
0
votes
0answers
24 views

convergence of self-consistent solution- vector of large no. of points

I have a matrix equation $\left(\begin{array}{cc} \frac{\delta^{2}}{\delta x^{2}}+\mu & D(x)\\ D(x) & \frac{\delta^{2}}{\delta x^{2}}+\mu \end{array}\right)\left(\begin{array}{c} u(x)\\ v(x) ...
8
votes
2answers
179 views

Representing Eisenstein numbers without floats

I have a project where I need to use quadratic fields Specifically numbers of the form $a + b \sqrt{-3}$ with $a,b \in \mathbb{Q}$. For example here are the prime numbers in Eisenstein integers: ...
0
votes
1answer
54 views

Least squares fitting

I have the following equation I came across which was solved using least squares $x = \sum_{n=1}^{N} A_{n} y_{n}$ Where $x$ is a $m \times p$ matrix and $y$ would be of size $m \times p$ as well ...
2
votes
0answers
73 views

Inverse problem with a rank-1 update

I hope you can help me out with this. I have to find the solution x to an inverse system $$ x=A^{-1}b $$ This inverse problem is basically a least square problem with a rank-1 update. $$ ...
1
vote
1answer
82 views

LSA, SVD and the Frobenius norm

In Latent Semantic Analysis one uses the SVD to perform a dimensional reduction of the term-document matrix, via the Eckart-Young theorem. Now, the rank $k$ approximation obtained by E-Y is proven to ...
3
votes
3answers
131 views

Efficient solver for a symmetric tridiagonal system where the upper/lower diagonals are offset

I'm looking for an efficient way to solve a symmetric tridiagonal system $Mx = d$, where the upper and lower diagonals of $M$ are offset from the main diagonal by $k$ rows/columns: $$ \begin{bmatrix} ...
1
vote
0answers
59 views

Lanczos algorithm with thick restart on a dynamic matrix

According to a recommendation, this is a re-post of that. currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries ...
0
votes
0answers
134 views

How to solve singular non symmetric poisson equation with Neumann boundary condtions?

I am trying to solve 2D Poisson equations with Neumann boundary conditions. When the mesh is uniform, Poisson equation is singular and symmetric, so the method listed in Null Space Projection for ...
5
votes
2answers
156 views

Applying matrix square root inverse in matrix-free regime

Let $A$ be a large symmetric positive definite matrix, and suppose that we can efficiently apply $A$ and have a fast solver to apply $A^{-1}$, but we do not have access to the matrix entries for ...
3
votes
2answers
184 views

Methods for solving linear systems

This is such a basic topic but there are so many different methods proposed for solving a linear system of equations. I recently found a very good source but couldn't really make sense of all the ...