Questions tagged [linear-algebra]

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

161 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
60 views

Can Representation Theory be studied computationally / numerically?

Can a subfield such as the representation theory of Lie algebras be studied computationally / numerically -- is there an interplay between the abstract and the concrete? I would be grateful for an ...
1
vote
0answers
60 views

Numerical methods. MDF (ILU) implementation

I am trying to implement Minimum Discarded Fill (MDF) Ordering algorithm for incomplete matrix factorization. The algorithm description is here on page 60 Preconditioning Techniques for a Newton–...
1
vote
0answers
68 views

implementation for coppersmith matrix multiplication

Is there any online implementation for the coppersmith matrix multiplication I have searched alot but can not find any? and if there is not any why is that Isn't this algotithm much faster than ...
1
vote
0answers
49 views

Does Boost provide a template implementation of the wedge product?

Does the boost C++ library implement the computation of the wedge product? The wedge product is mentioned here, but it is not very clear (to me at least) whether there is a template implementation of ...
1
vote
0answers
81 views

What's the more efficient way to solve this matrix equation?

This is intended to be a more generic question not about a specific system. Given a hermitian matrix $H(x_1,\dots,x_n)$ depending non-linearly on some real parameters $x_1,\dots,x_n$. We want these to ...
1
vote
0answers
58 views

Kinetic preconditioning

Publication arXiv:0804.2583 describes a method for doing self-consistent iteration without having to diagonalize the Hamiltonian operator at every step. IX. PRECONDITIONING As already mentioned, ...
1
vote
0answers
53 views

Stability of SVD, Eigendecompositions, and pseudoinverse procedures in modern LAPACK routines

I have proposed an optimisation algorithm which I claim has improved upon the previous algorithm in a number of ways. One of these claims is that my proposed solution requires no explicit SVD and ...
1
vote
0answers
101 views

Connection between piecewise linear basis functions and RELU activation function

ReLU activation is defined as follows $$\sigma(x)=\max(0, x).$$ Let's assume that I have deep network of 1 hidden layer, than output from my layer has form $$ f(x)= \sigma(Wx +b), $$ where matrix W ...
1
vote
0answers
53 views

Methods to compute specific eigenvector components for a tridiagonal matrix

I have an application that is somewhat similar to the situation of computing Gaussian quadrature nodes and weights: simply put, I need to compute the eigenvalues and the last two (normalized) ...
1
vote
0answers
45 views

What is a performant clustering algorithm for approx 10,000 vectors of approx 30 dimension?

I have a set of real-valed vectors, for example $S = \{v_1, v_2, ..., v_k\}$ $v_i = \begin{pmatrix} age_i \\ height_i \\ weight_i \\ ... \end{pmatrix}$ or whatever. Each vector has on the order of ...
1
vote
0answers
255 views

Multithreading determinant computation of a Big Matrix

I've been trying to design an algorithm for computing determinant of Big square Matrices (N <= 1000). I am allowed to use multithreading, but still, I can't design the algorithm. The assignment ...
1
vote
0answers
344 views

Is reduced stiffness matrix positive definite too?

The stiffness matrix $K$ in a finite element analysis is a symmetric positive definite matrix. When we introduce essential boundary conditions, we remove rows and columns associated with prescribed ...
1
vote
0answers
102 views

Low memory algorithm for matrix diagonalisation

I'm trying to find the largest eigenvalues of very large $N \times N$ matrices ($N = 10^{10}$ and larger). The matrices are not sparse but the multiplication operation is fast. For now, I'm using ...
1
vote
0answers
40 views

Name for vectors in a Krylov space but not the preceding one

It seems to me that a useful concept to define when studying Krylov subspace methods is the idea of a vector that belongs to a Krylov subspace $\mathcal{K}_{n+1}(A,b)$ but not to the preceding one $\...
1
vote
0answers
59 views

Algorithm design to filter on 5,000 stocks each of which has 4 months worth of data points

I want to filter on 5000 stocks, each of which has 4 month or more worth of data (>= 500 data points each). my filtering criteria will be based on 8 calculated values from the data points. for example,...
1
vote
0answers
78 views

Successive iteration method for solving eigenvalue ploblem

I have a question concerning the branch of successive iteration methods (Newton, Runge-Kutta). I definitely know (or can read in Wikipedia) the implementation of these methods. But I was wondering ...
1
vote
0answers
173 views

Linear regression with inequality constraint in Java

I haven't been doing math in years and I'm facing the following problem. I'm trying to implement in Java a linear regression under a set of inequality constraints. Sorry in advance for all the ...
1
vote
0answers
48 views

Selecting n points to have a given mean and covariance

I have a set $N$ points in $d$-dimensional space, $\mathbf{x}_i \in \mathbb{R}^d ~~ \forall i=\{1,2,...,N\}$. How to choose $n$ points from the set such that it maximises $$ f = |\mathbf{S}|^{-n/2} \...
1
vote
0answers
166 views

Numerical Precision in Matrix Inversion Routines

Let's say I have a matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$, and its associated inverse, $\mathbf{A}^{-1}$. The elements of $\mathbf{A}$ are given in IEEE single precision, i.e. 23-bit mantissa, ...
1
vote
0answers
213 views

How to make LAPACK eigenvectors orthogonal like Matlab?

I'm using LAPACK zgeev to calculate eigenvectors of a symmetric complex matrix of high dimensions ($n \approx 2000$). I need these eigenvectors to satisfy $$\sum_{...
1
vote
0answers
48 views

How is the Gastner-Newman equation implemented to create value-by-area cartograms?

There is a paper called "Density-equalizing map projections: Diffusion-based algorithm and applications" by Michael T. Gastner and M. E. J. Newman, which explains their algorithm (which is based in ...
1
vote
0answers
137 views

Eigenvalues using QR iteration

I'm trying find the eigenvalues of a matrix A using QR iteration with Householder. I used this code which I found from Cornell University that decomposes QR with Householder. ...
1
vote
0answers
60 views

Reduce large sparse linear operators to memory efficient loops?

I'm dealing a lot with large sparse linear operators these days and I'm quite new to them. A lot of the matrices I deal with originate with only a few unique integers, however, there are lots of them. ...
1
vote
0answers
204 views

All eigenpairs of large sparse symmetric matrix

In advance I am sorry for my noobish question. I am a physics PHD student and basically I use python for my math/physics problems. But now I have a problem which requires more computing capacity and ...
1
vote
0answers
94 views

QR via Householder: less computationally complex variants?

I'm a probabilist and need to do a few computations for a rather big linear least squares problem, so I'm trying to optimize the computation as far as is feasible to me. In computing the QR ...
1
vote
0answers
65 views

Closed-form Jacobian of se3 element w.r.t. 6-dof motion

Let $A$ and $B$ be two rigid transformations in 3D space that transform things from global to local coordinates. Let their relative transformation be expressed by $W=A*B^{-1}$. $W$ can also be ...
1
vote
0answers
285 views

How to obtain projections from sinogram in ART reconstruction technique?

I'm kind new in the Computed Tomography field and I'm trying to understand and implement ART technique. Said it, I started to read the book The Mathematics of Medical Imaging - A Beginners Guide by ...
1
vote
0answers
65 views

What's the optimal method to solve for the top eigenvectors of a very large, real, symmetric matrix of limited rank?

Consider a real symmetric matrix of dimension N~10^5 and rank m~2000. What is the most efficient algorithm for determining the top m eigenvectors? If the answer isn't obvious, are there existing ...
1
vote
0answers
56 views

bound error for iterative method for solving linear system

$A$ is square and positive definite, and let $r_k = Ax_k - b$. Also let $M = \frac{1}{2}(A+A^T)$. I want to show that $$\frac{||r_{k+1}||_2}{||r_k||_2} \le \left(1-\frac{\lambda_\min(M)^2}{\lambda_\...
1
vote
0answers
61 views

Efficiently computing the properties of a Chebyshev series

Suppose we have some function $f(x)$ defined as a Chebyshev series up to order $M$: $$ f(x) = \sum_{n=0}^{M} c_n T_n(x). $$ For a given coefficients vector $\mathbf{c}$, and $x \in [-1,1]$ I'm ...
1
vote
0answers
116 views

How to get the eigenvalues of Hamiltonian in an over complete basis

Let $|\psi_i\rangle$, $i=1...N+m$, be a set of overcomplete basis vector in a $N$-dim Hilbert space. The following are known: (Einstein's summation convention assumed) $$\hat{H}|\psi_i\rangle=H_{ji}|\...
1
vote
0answers
137 views

Updating factorization of Laplacian (add/remove edges)

For a graph $G=(V,E)$, recall that the unweighted Laplacian is $L:=D^\top D$, where $D\in\{-1,0,1\}^{|E|\times|V|}$ is the graph "gradient" operator that subtracts adjacent vertex values onto edges. ...
1
vote
0answers
34 views

Difference between Chebyshev first and second degree iterative methods

Consider linear equation $Au = f$. We want to solve it with iterative method (assuming $A$ is good). First order iterative method is: $$ u^{k+1} = u^k - \alpha_{k+1}(Au^k - f), $$ The second degree ...
1
vote
0answers
370 views

Preconditioned Steepest Descent

For my program assignment I need to write a preconditioned steepest descent algorithm. I have psedo-code from my professor which is here: From reading in my text on this method they say that $P$ is ...
1
vote
0answers
105 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) \sin(...
1
vote
0answers
96 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 ...
1
vote
0answers
112 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 ...
1
vote
0answers
155 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 $\{...
1
vote
0answers
56 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} \left(\begin{array}{c}1\\...
1
vote
0answers
153 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
0answers
61 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: I'...
1
vote
0answers
92 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 ...
1
vote
0answers
382 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
96 views

Sparse matrix factorization of a rank deficient matrix by decomposition into linearly independent components

I've got a little conjecture I need to prove for a theoretical result related to causal Bayes net search with latent variables under sparsity constraints. If you're interested in the application ...
1
vote
0answers
260 views

Markowitz Pivoting to reduce size of a dense integer system

I am dealing with a large sparse integer matrix that I need to find the nullspace of. I've seen Markowitz Pivoting come up in several places discussing similar problems such as here: http://www....
1
vote
0answers
145 views

Efficient way to do congruent transformation using matrix inverse?

I know a square self-adjoint matrix $S_{vv}$ and I want to find: $S_{rr} = HS_{vv}H^{\dagger}$ where $\dagger$ denotes conjugate transpose. I do not know $H$ but I do know $H^{-1}$. What is the ...
1
vote
0answers
981 views

Pixel-To-Angle Transformation in Camera Image

I'm trying to localize points I see in a camera image in terms of azimuth and elevation and match points between shots. Individual shots should differ only in rotation around the camera's center (...
1
vote
0answers
28 views

PCA performed on a configuration with scaled axes

Suppose a configuration $X\in\mathbb{R}^{n\times 2}$ is output of PCA on some high-dimensional data $Y\in\mathbb{R}^{n\times h}$. Note that this PCA is performed by $$X=Y\cdot U,$$ where columns of $U$...
0
votes
0answers
60 views

How to make a directed graph symmetric?

Say I have a directed graph given as an adjacency matrix $A$ in CSR format represented by the arrays ia (row indexes) and ja (...
0
votes
0answers
47 views

Formula for overdetermined logical matrix pseudoinverse not requiring SVD?

In https://commons.wikimedia.org/wiki/File:YI_%3D_PI.png, you will find a formula-based solution for an overdetermined logical matrix pseudoinverse. This simple formula gives the same result as the ...