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.
171
questions with no upvoted or accepted answers
3
votes
0answers
331 views
Computing eigenvectors from the QR algorithm
I've seen a few other posts on this topic but none have full answers.
I'm trying to implement some eigen-decomposition algorithms. I've managed to get the Explicit QR algorithm and the Implicit (...
3
votes
0answers
187 views
Find constrained vectors maximizing angles between them - methods?
This is related to a question I had asked earlier, with the distinction that earlier I did not have a non-linear objective functional to minimize. The problem is reproduced below with added ...
3
votes
0answers
388 views
On solution of a class of discrete-time Lyapunov equation for systems with multiplicaitve noise
Let's consider the following equation
$$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$
where $p$ is an positive integer and $C$ is a known positive semidefinite matrix. If we augment $F=[F_{1}...F_{p}]$ ...
3
votes
0answers
173 views
How to accurately decompose positive semidefinite matrix and use the lower triangular part in linear equations
I have $n$ arbitrary $p\times 1$ vectors $x_i$, and $p\times k$ matrices $A_i$, and $n$ $p \times p$ positive semidefinite matrices $S_i$, where some (often most) of the $S_i$'s are same (for example ...
3
votes
0answers
104 views
Efficient principal pivots
It was suggested I should try posting this question here from Mathematics
Background
I'm working on a numerical linear algebra package in C#. I'm trying to implement a variety of "principal ...
3
votes
0answers
116 views
Up-/downdating methods for a series of normal equations
In an application I have to solve a series of positive definite linear systems of the form $A^TA x = A^Tb$ (i.e. normal equations). The next system is obtained from the previous one by adding and/or ...
2
votes
0answers
59 views
Software for solving large systems of linear equations over gf(2)
What available solvers are there for linear equation solver over GF(2) (Boolean), capable of dealing with large sparse systems (in the 10k - 100k variables range)?
2
votes
0answers
42 views
How to solve this boundary value problem which has more unknown than equation on MATLAB
I need your helps about solving the problem below with MATLAB. I am trying to solve 2D Stress Wave Propagation problem by using FDTD(Finite difference time domain) method on the cylindrical coord. I ...
2
votes
0answers
84 views
Algorithm for computing inner products multiple times
I am taking a computational linear algebra course and i got stuck during a homework problem concerning the computation of inner products. I am supposed to compute the inner product:$$\mathrm{a}_{\...
2
votes
0answers
76 views
Why is LAPACK (seemingly) suboptimal for packed and banded eigenvalue problems?
Based on this LAPACK routines list, it looks like there is no relatively robust representation (RRR) driver routine for either packed or banded symmetric eigenvalue problems. According to the relevant ...
2
votes
0answers
38 views
Is there a published RQ decomposition column-major algorthm?
I am refactoring an existing algorithm where where a RQ decomposition (as opposed to the more common QR) would be rather useful.
Most common books on the subject (e.g. Golub and Van Loan) discuss QR ...
2
votes
0answers
90 views
Solving a huge least squares system of equations when I can only evaluate Ax
I have a situation where I can generate a system of $M$ linear equations for $N$ variables ($N \ne M$). Implicitly this is of the form $Ax=b$ with $A \in \mathbb{R}^{M \times N}$, although I never ...
2
votes
0answers
55 views
Avoid matrix multiplication in algebraic multigrid method
Currently when I try to solve a linear algebra system of the form of $A x =b$ I use the algebraic multigrid method. The algebraic multigrid method uses a Galerkin product to form the coarse grid ...
2
votes
0answers
48 views
Fitting a plane with the Prewitt gradient operator
Prewitt gradient operator
Show that the Prewitt gradient operator can be obtained by fitting the least-squares plane through the 3 × 3 neighborhood of the intensity function.
Hint: Fit a plane to ...
2
votes
0answers
104 views
Small residual but wrong results
When I use BiCGStab to solve a linear matrix system, I use the relative residual to exit the iteration and output the results. For calculating the relative residual I divide the norm of vector $r$ ...
2
votes
0answers
41 views
Inverses of many standard subspaces of one large matrix
i have a large rectangular invertible matrix M (about 5000x5000) and i have a loop in which i do the following for each iteration i (there are about 6000 iterations):
i am given a subspace S_i (which ...
2
votes
0answers
223 views
Regularized least squares with QR factorization
Consider the regularized least squares problem
$$
\min_x || b - A x ||^2 + \lambda^2 ||x||^2
$$
which is equivalent to
$$
\min_x \left|\left| \pmatrix{b \\ 0} - \pmatrix{A \\ \lambda I} x \right|\...
2
votes
0answers
31 views
Randomized Submatrix of a Sparse Matrix
I have a sparse square matrix $A$ with size $n \times n$ and number of nonzero entries $nnz$.
The goal is making a sub-matrix $B$ with $s$ nonzeros which are randomly chosen from $A$. Duplicates are ...
2
votes
0answers
477 views
finding null space to a complex matrix
I need to solve the following equation:
$$
\begin{pmatrix}
\frac{\omega^2}{c^2}\varepsilon_x-\mu_z^{-1}k_y^2-\mu_y^{-1}k_z^2 & \mu_z^{-1}k_xk_y & \mu_y^{-1}k_xk_z\\
\mu_z^{-1}k_xk_y &\...
2
votes
0answers
69 views
Simultaneous update to barycenters
Suppose a tiling is given in 2D (an embedding of a planar triangulated graph), with all faces convex.
Now suppose one moves each point, one by one, to the barycenter of its neighbors. I think that ...
2
votes
0answers
125 views
Efficiently solve linear system with matrix quadratic form
Take the system $$A^TCAx=b$$
where $$A\in\mathbb{R}^{n\times m},\;C\in\mathbb{R}^{n\times n},\;x,b\in\mathbb{R}^{m}, \;m\leq n$$ and $$A^TA=I$$ and $$Cy=d$$ can be solved efficiently in general (...
2
votes
0answers
100 views
Acceleration of matrix geometric series
Suppose we want to find $x$ such that:
$$x=b+Ax$$
where $A$ is a large sparse square matrix with eigenvalues in the unit circle.
There are two representations of the solution:
1)
$$x=(I-A)^{-1}b,$$...
2
votes
0answers
65 views
Parallel compact schemes using the Parallal Diagonal Dominant (PDD) algorithm
I would like to use the PDD algorithm developed by Sun to solve tridiagonal matrices in parallel for the following compact finite difference scheme:
$
\begin{align}
\dfrac{1}{4}f^{'}_{i-1} + f^{'}_i +...
2
votes
0answers
259 views
Finding integer/lattice points (coordinates) inside a polytope/polyhedra?
I am using Python but I wouldn't mind changing language. All I have gotten from my research are tools to count the number of (lattice) points inside a region given the equations for the planes that ...
2
votes
0answers
40 views
Deterministic method to compute “Process noise covariance matrix, Q” for a Kalman filter when parameter variations of the model is known apriori
I am implementing a Kalman filter (for a linear ODE system for now).
My model represents a physical device that has 6 "parameters", i.e. those values of the device do not evolve over time (within a ...
2
votes
0answers
72 views
How can I numerically solve a saddle point problem with repeated constraints?
I am interested in numerically solving the following constrained minimization problem; Find the value of $x\in \mathbb{R}^n$ that minimizes $f$ where
$f\colon \mathbb{R}^n\to \mathbb{R}$ is defined ...
2
votes
0answers
288 views
Connectivity and Clustering using Eigenvectors and the Fiedler Vector
Going off of the answer here:
sorting adjacency matrix by the Fiedler vector
So here, Jesse the answerer plotted the first 3 eigenvectors associated with non-zero eigenvalues of the Laplacian against ...
2
votes
0answers
667 views
Does applying the Newton-Raphson iteration for matrix reciprocal refine a matrix inverse from LU/GE?
This is a follow-up to this answer.
Suppose you have a possibly very ill-conditioned matrix $A$, and you compute its inverse with LU/GE to get $X_{\text{lu}}\approx A^{-1}$.
The Newton-Raphson ...
2
votes
0answers
101 views
Eigenvalue decomposition of the sum: $AA^T$ + diag($u$)
Suppose $A\in\mathbb{R}^{n\times c}$,$u\in\mathbb{R}^n$,$n\gg c$.
The time complexity of eigenvalue decomposing directly for matrix $AA^T+\text{diag}(u)$ is $O(n^3)$. And it is easy to avoid $O(n^3)$ ...
2
votes
0answers
55 views
Optimal ordering in Jacobi SVD algorithm
In Jacobi SVD algorithm as given here every pair of columns of the matrix is orthogonalized until convergence. I want to know that how does the order of selection of the pair of columns affect the ...
2
votes
0answers
304 views
Quasi Newton method for block diagonal Hessian
I am having an unconstrained optimization problem, where the Hessian is positive semidefinite and block diagonal. The function is strictly convex, hence, the curvature condition ($ s^{T}_{k}y_{k} > ...
2
votes
0answers
52 views
SPECT reconstrction using MLEM
In Single-Photon Emission Computerized Tomography (SPECT) parallel beam reconstruction using Maximum-Likelihood Expectation–Maximization(MLEM), is it sufficient to scan the object around 180 degree? ...
2
votes
0answers
81 views
Does there exist a Fourier transform algorithm for perturbed data?
Assuming I have a length-$n$ real vector $x$ and have already computed its Fourier transform $\hat x$ (in time $O(n\log n)$), I would like to compute the Fourier transform of $y = x + \delta x$, where ...
2
votes
0answers
256 views
Does Conjugate Residual really have convergence properties similar to that of Conjugate Gradient?
I have coded up a toy implementation of Conjugate Residual and have been testing it. Both wikipedia and the Saad claim that Conjugate Residual and Conjugate Gradient have similar convergence behavior....
2
votes
0answers
184 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 & B_v^...
2
votes
0answers
126 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 ...
2
votes
0answers
308 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
0answers
143 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 ...
2
votes
0answers
123 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 imaginary ...
2
votes
0answers
189 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 ...
2
votes
0answers
404 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
0answers
746 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 ...
2
votes
0answers
138 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.
$$
x=[uv^{T}...
2
votes
0answers
987 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 ...
2
votes
0answers
102 views
Preconditioner for large size hermitian eigenvalue problems
Basically I try to compute several smallest eigenvalues of some sparse 50k*50k eigenvalue problems using matlab.
$$Ax = \lambda Bx$$
With matlab eigs, it's not as fast as I expected. So I tried some ...
2
votes
0answers
126 views
Lapack++ for QR algorithm
I have recently started using Lapack++ which I found convenient for my programming purpose, in general.
Now, I need to solve a matrix using QR algorithm. I've searched the user manual
and I found a ...
2
votes
0answers
75 views
Estimating eigenvalues from time-dependent non-linear operator
I have a very sparse non-linear system $N(u) = 0$ that can be solved as a time-dependent ODE, $\frac{du}{dt} = N(u)$, and explicitly integrated until $\frac{du}{dt} = N(u) = 0$, e.g. by forward euler, ...
2
votes
0answers
157 views
How do I implement thin plate splines with barriers?
I want to implement thin spline interpolation of scattered elevation data $ \{z_i(x_i,y_i)\}_{i=1..n} $ in C++.
This seems fairly simple using Radial Basis Functions:
$$ z(x,y) = p(x,y) + \sum_i l_i\...
2
votes
0answers
655 views
Finding a permutation that makes a matrix lower triangular
I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
1
vote
0answers
78 views
Matlab - Equality between 2 Fisher matrices constructed in a different way
I want to know if, on a Fisher matrix, the projection operation (with a Jacobian matrix) commutes with a matricial inversion operation.
The 2 ways to build these 2 matrices are:
1) First method:
1.1) ...
