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.

Filter by
Sorted by
Tagged with
12
votes
1answer
2k views

weighted SVD problem?

Given two matrices $A$ and $B$, I'd like to find vectors $x$ and $y$, such that, $$ \min \sum_{ij} (A_{ij} - x_i y_j B_{ij})^2. $$ In matrix form, I'm trying to minimize the Frobenius norm of $A - \...
9
votes
3answers
475 views

Computing the characteristic polynomial of real sparse matrix

Given a generic sparse matrix $A \in \mathbb{R}^{n\times n}$ with m << n (correction: $m \ll n^2$) non-zero elements (typically $m \in {\cal O}(n)$). $A$ is generic in the sense that it has no ...
7
votes
1answer
310 views

float128 in linear algebra

Is there any paper or research concerning float128 arithmetics applied to linear algebra problems(e.g. iterative solvers, decompositions etc.)? How much benefit is really there in comparison with ...
3
votes
1answer
70 views

2D Jacobi line maintenance?

Suppose a linear system is given $$AX=B,$$ where $A\in\mathbb{R}^{n\times n}$ is a symmetric strictly diagonal matrix, and $X, B\in\mathbb{R}^{n\times 2}$. Therefore, the 2D Jacobi iterative solver is ...
12
votes
3answers
1k views

Efficient tridiagonal matrix algorithm implementation

I am solving a physical problem using implicit numerical scheme. This leads me to solving a linear equation with tridiagonal matrix. I've coded this algorithm from Wikipedia. I wonder if there is an ...
9
votes
3answers
897 views

Iterative methods for indefinite systems without block structure

Indefinite systems of matrices appear for example in the discretization of saddle point problems by mixed finite elements. The system matrix can then be put in the form $$\begin{pmatrix} A & B^t \...
7
votes
1answer
608 views

Jacobi iteration to reduce the quadratic function

Given certain function $f(X)$ which is quadratic in $X\in\mathbb{R}^{n\times d}$, $$\frac{1}{2}tr(X^TAX) - tr(Y^TBX)$$ for positive definite weighted Laplacian matrices $A, B\in\mathbb{R}^{n\times n}...
5
votes
2answers
3k views

Fast algorithms to find the eigenvalues of some matrix on intervals of interest

I am curious how to quickly compute the eigenvalues for arbitrary matrices, sparse or dense, restricted on some given interval of interest. Suppose we have an arbitrary $n\times n$ matrix $A$, ...
37
votes
4answers
31k views

How does the MATLAB backslash operator solve $Ax=b$ for square matrices?

I was comparing a few of my codes to "stock" MATLAB codes. I am surprised at the results. I ran a sample code (Sparse Matrix) ...
5
votes
2answers
531 views

Recommendation for a good article/book for frontal methods?

Can someone provide an article or book that explains the principle used in frontal solvers? Some examples also may help understand the frontal methods better.Thanks in advance!
6
votes
1answer
281 views

Question about the smoothing operators in multigrid methods for nonlinear PDEs

Suppose we are dealing with a nonlinear problem, say $$ A u := L u + G(u) = f $$ the nonlinearity of the operator $A$ is the polynomial type, ie, $L$ is a linear operator, and $G(u) = u^k$, or ...
11
votes
1answer
600 views

Computing standard errors for linear regression problems without calculating inverse

Is there a speedier way to calculate standard errors for linear regression problems, than by inverting $X'X$? Here I assume we have regression: $$y=X\beta+\varepsilon,$$ where $X$ is $n\times k$ ...
11
votes
1answer
456 views

How to establish that an iterative method for large linear systems is convergent in practice?

In computational science we often encounter large linear systems which we are required to solve by some (efficient) means, e.g. by either direct or iterative methods. If we focus on the latter, how ...
4
votes
2answers
193 views

Looking for a mathematical proof of stability in floating point arithmetic of CG - any reference?

I am looking for a reference - paper, book, discussion, anything that has a mathematical proof for stability of the conjugate gradient method in floating point arithmetic. Something similar for ...
2
votes
2answers
250 views

Algorithm to compute the intersection of meshlines with a boundary

I need a program or an algorithm that computes the intersection of a mesh and a boundary. The mesh is structured orthogonal in nature and the boundary is a circle (for example). This will be used ...
10
votes
3answers
3k views

How to construct a prolongation and restriction operator for an algebraic multigrid solver?

I am trying to solve a linear system of equations that is sparse, but lacks any kind of banded structure. I have heard that there is a way to extend the principles of a multigrid solver for implicit ...
11
votes
3answers
1k views

Which linear algebra texts should I read before learning numerical linear algebra?

Assuming one wishes to study numerical linear algebra in depth (and follow journals on numerical linear algebra and matrix theory), which would be a better course/better book to take up at first: ...
7
votes
1answer
893 views

Sparse hermitian eigensystems: are there better techniques than Arpack or TRLan?

As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
4
votes
2answers
180 views

What mapping strategy should I use when solving many large linear systems of equations?

I am working on a problem that involves solving many (thousands) of distinct linear systems of equations, each with thousands of variables. Let's assume that the size of each matrix is exactly the ...
4
votes
1answer
779 views

Diffusion kernel “guide”

Diffusion kernels are kernels which "project" information about graphs into $R^n$ so that certain machine learning techniques can be performed. I have read through this paper and feel fairly ...
7
votes
1answer
175 views

Conjugate Gradient with Hierarchical Basis Functions: How can the hierarchical base be decomposed?

I'm trying to implement a Conjugate Gradient solver using Hierarchical Basis Functions, following this paper. In section 3 the paper says that the hierarchical basis matrix $S$ can be decomposed into ...
14
votes
2answers
2k views

How useful is PETSc for Dense Matrices?

Wherever I have seen, PETSc tutorial/documents etc. say that it is useful for linear algebra and usually specifies that sparse systems will benefit. What about dense matrices? I am concerned about ...
11
votes
1answer
1k views

How can I compute a basis for a matrix Lie algebra given a finite set of generators?

Given an arbitrary set of (numerical) square complex matrices $\mathcal{A}=\{A_1,A_2,\cdots,A_m\}$, I am interested in computing the real matrix Lie algebra generated by $\mathcal{A}$, call it $\...
6
votes
2answers
345 views

What guidelines should I use when choosing a scalable linear solver?

There are many different linear solvers, some which work best for diagonally dominant matrices, some for symmetric, some for positive definite ones, some for banded matrices, etc... There are direct ...
3
votes
1answer
893 views

Is a checkerboard block decomposition of a matrix useful when solving a linear system with a parallel conjugate gradient method?

According to these lecture notes, a checkerboard block decomposition should exhibit better scalability when applied to parallel matrix-vector multiplication (presumably because of greater cache hit ...
6
votes
5answers
435 views

Where do dense matrices occur?

I have primarily dealt with Dense Matrices arising from Electrodynamics. However, I am interested in knowing where else Dense Matrices occur. I am especially interested in knowing where they occur in: ...
5
votes
3answers
797 views

Seemingly non-unique Cholesky factor via QR rectangularisation

I am trying to implement an algorithm from a paper which makes use a QR factorization of a real matrix $A$ as a means of one of forming the Cholesky factor of $A^T A$ without explicitly forming $A^T A$...
5
votes
2answers
1k views

Sufficient conditions to ensure convergence of the conjugate gradient method

I know that a conjugate gradient method is guaranteed to converge to the solution of a linear system if the matrix is positive definite. I'm working with a family of matrices that have the following ...
3
votes
1answer
286 views

How to solve a problem with structure similar to a finite difference discretization of the 2D Poisson equation, but with non-symetric coefficients?

Recently, I've been asking about methods to solve a finite difference discretization of the 2D Poisson equation (see here and here) of the form: $$U_{i-1,j} + U_{i+1,j} -4U_{i,j} + U_{i,j-1} + U_{i,...
23
votes
4answers
4k views

When do orthogonal transformations outperform Gaussian elimination?

As we know, orthogonal transformations methods (Givens rotations and Housholder reflections) for systems of linear equations are more expensive than Gaussian elimination, but theoretically have nicer ...
10
votes
2answers
3k views

What's the most efficient way to compute the eigenvector of a dense matrix corresponding to the eigenvalue of largest magnitude?

I have a dense real symmetric square matrix. The dimension is about 1000x1000. I need to compute the first principal component and wonder what the best algorithm to do this might be. It seems that ...
6
votes
4answers
279 views

Approximately “solving” a linear system of equations without a feasible solution

A linear system of equations has the form $Ax = b$, where a matrix $A$ and a vector $b$ are given, and I wish to find a solution vector $x$. Suppose that the system $Ax = b$ has no feasible solution. ...
3
votes
1answer
2k views

Problems running a PETSc example in parallel

After configuring and building PETSc, I have successfully been able to run several examples. In particular, I am working with this example. I have been able to run the program using the following ...
7
votes
4answers
2k views

precision vs matrix condition number

I have an application in which I am computing a quantity which is approximated by an average over $M$ points. In theory, the average converges to the correct quantity when $M$ is infinite. In practice,...
10
votes
1answer
6k views

Are there any heuristics for optimizing the successive over-relaxation (SOR) method?

As I understand it, successive over relaxation works by choosing a parameter $0\leq\omega\leq2$ and using a linear combination of a (quasi) Gauss-Seidel iteration and the value at the previous ...
9
votes
2answers
857 views

Which Sparse Matrix Solver Libraries can I run on Android?

The title says most of it. I'm looking for a lightweight and easy-to-use library that I can use for Android (NDK) projects. For dense stuff I like using Eigen but I haven't found many comprehensive (...
2
votes
2answers
990 views

Lanczos solver implementations in MATLAB/C++ give different results

I have transferred my MATLAB Lanczos solver for symmetric eigenvalue solvers to C++ with the help of Intel MKL and MTL4 libraries. I have some wrapper templates for MKL routines. However during the ...
9
votes
1answer
1k views

Schrodinger equation with periodic boundary conditions

I have a couple of questions regarding the following: I am trying to solve the Schrodinger equation in 1D using the crank nicolson discretization followed by inverting the resulting tridiagonal ...
8
votes
3answers
3k views

Solving a non-symmetric non-diagonally dominant sparse system the best way

I faintly recall from my early "numerics" lectures that iterative linear solvers for $Ax=b$ often require that when $A$ is decomposed as $$A=D + M$$ where D is a diagonal matrix and $M$ has zero ...
5
votes
2answers
471 views

How to parallelize a banded direct solver?

I have a linear system whose matrix that is diagonally dominant, non-symmetric, but banded. Since the band-radius is 2 (producing only 5 variables per equation), a banded direct solver (gaussian ...
15
votes
1answer
2k views

Can a Krylov subspace method be used as a smoother for multigrid?

As far as I am aware, multigrid solvers use iterative smoothers such as Jacobi, Gauss-Seidel, and SOR to dampen the error at various frequencies. Could a Krylov subspace method (like conjugate ...
11
votes
1answer
2k views

How can one parallelize a multigrid method for solving a linear system of equations?

As I understand it, the multigrid method solves a linear system by solving a coarser version of the same problem (there by eliminating low frequency error) then projecting back to the fine grid to ...
3
votes
0answers
114 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 ...
8
votes
1answer
3k views

What is a good stop criterion when using an iterative method to find eigenvalues?

I read this answer, and realized I have been using the difference between sucessive iterates to define a stop criterion for an iterative method of finding eigenvalues/vectors. What are good stop ...
27
votes
2answers
12k views

Why is my iterative linear solver not converging?

What can go wrong when using preconditoned Krylov methods from KSP (PETSc's linear solver package) to solve a sparse linear system such as those obtained by discretizing and linearizing partial ...
6
votes
2answers
691 views

Is it possible to dynamically resize a sparse matrix in the Petsc library?

This may be a Petsc newbie question, but... I'm using Petsc to solve a large sparse linear system. The initial creation of the matrix is fairly slow, which I'm given to understand is largely due to ...
4
votes
1answer
94 views

Applicability of combinatorial and support preconditioner

There are several correspondences between matrices and graphs, e.g., each matrix is the adjacancy matrix of a weighted graph. The terms support preconditioner or combinatorial preconditioner refer to ...
9
votes
1answer
287 views

Nested dissection on regular grid

When solving sparse linear systems using direct factorization methods, the ordering strategy used significantly impacts the fill-in factor of non-zero elements in the factors. One such ordering ...
12
votes
3answers
351 views

In what application cases are additive preconditioning schemes superior to multiplicative ones?

In both domain decomposition (DD) and multigrid (MG) methods, one may compose the application of the block updates or coarse corrections as either additive or multiplicative. For pointwise solvers, ...
3
votes
2answers
818 views

Linear regression via SVD not producing best fit with escalating polynomial degree

I am using a basic singular value decomposition (via LAPACK) routine in FORTRAN to solve an overdetermined system in the form of $A\cdot X = B$ where $\mathrm{size}(A) = [m,n]$ with $m > n$. My ...