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
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
39 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
83 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
75 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
79 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
51 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
44 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
94 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
178 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
348 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
123 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
91 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
168 views
Left eigenvectors using ARPACK
I'm trying to find both the dominant $k$ left and right eigenvectors, that is,
$$V_L\mathcal{A} = \Lambda V_L\\
\mathcal{A}V_R = V_R\Lambda\\
V_LV_R = I_{k\times k}$$
$V_L$ being the $k\times N$ ...
2
votes
0answers
64 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
239 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
39 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
68 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
283 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
523 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
100 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
300 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
79 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
240 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
171 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
124 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
297 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
138 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
182 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
355 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
680 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
134 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
964 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
100 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
124 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
644 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
58 views
Upper bound on condition number in linear preconditioning
I'm studying iterative methods for solving linear system, and I find the following setting in Wikipedia:
Consider a matrix splitting $A = M-N$, where $A,M,N$ are all symmetric and positive definite ...
1
vote
0answers
62 views
Given an unpivoted form of Aasen's algorithm, how does one add pivoting?
I've implemented the version of Aasen's algorithm described in the book Matrix Computations 4th Edition. The version there doesn't have pivoting. The book's description of how to add pivoting is a bit ...
1
vote
0answers
25 views
Multiplying by E[xy'] where only some statistics of xy' are known
(cross-posted on crossvalidated)
For random variable $(x,y)$ in $\mathbb{R}^{d}\times \mathbb{R}^{d}$ and vector $v \in \mathbb{R}^d$, I need to perform the following matrix vector multiplication.
$$T(...
1
vote
0answers
44 views
Triangle on top of diagonal least squares
I need to solve many least squares problems with the following matrices:
$$
\pmatrix{ R \\ D_i }
$$
where $R$ is upper triangular and $D_i$ is diagonal. $R$ is the same for all the problems, while $...
1
vote
0answers
36 views
Choosing the pivot for the rotation matrix in similarity transformation
I have arrived at an equation in the similarity transformation -
$M_r$ = $T. M_{r-1}. T^t$ ,where $T$ is the rotation matrix and $M_r$ ,$M_{r-1}$ are similar matrices. My aim is to find the rotation ...
