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.
942
questions
0
votes
1answer
41 views
How to optimize nuclear norm subject to positive semidefinite constraints?
For finite dimensional symmetric positive semidefinite matrices $A$ and $B$, I would like to solve
\begin{align}&\min |X - A|_1 \\
&\text{subject to}\\
&X \preceq B \\
&0 \preceq X\...
0
votes
0answers
55 views
Derivative-free ill-conditioned non-linear least squares
I am looking for a package which can solve (non-linear) least squares problems without the use of derivatives (because of an expensive model), but which also deals with ill-conditioning well (such as ...
7
votes
5answers
443 views
Checking singularity of a matrix
Suppose that we don't know $n \times n$ matrix $A$ explicitly but we are only able to compute products $Ax$ where $x$ is a column vector with $n$ elements. Is there an algorithm to determine whether $...
0
votes
3answers
69 views
How to determine global stiffness matrix is constrained or not
Background
In solid fem, we often solve $$\mathbf{Ku}=\mathbf{p}$$
where $\mathbf{K}$ is global stiffness matrix, $\mathbf{u}$ is displacement, $\mathbf{p}$ is global load vector.
If displacement not ...
-1
votes
0answers
28 views
How to generate a symmetric matrix that will produce a pos-def matrix after application of a pos-def kernel function?
Note in advance that I'm not trying to sample symmetric, positive-definite matrices - that, at least, I know how to do.
What I'd like to sample, is symmetric matrices (ideally with diagonal 0, ...
2
votes
1answer
80 views
Efficient projection of a vector onto matrix kernel
Given an $m \times n$ matrix $A$ and a vector $x\in\mathbb R^n$, with $m<n$, what's an efficient way of computing the projection of $x$ onto the kernel of $A$?
7
votes
2answers
256 views
Is there an iterative solver for dense matrices with possible zero diagonal entries?
Is there an iterative solver that can handle potentially zero entries on the central diagonal? I am implementing a polynomial fitting algorithm (up to $10^{th}$-order) and my matrix is a "...
2
votes
1answer
186 views
Solution of the linear system using Sherman-Morrison formula for 1000000x1000000 (7450.6GB) matrix using MATLAB
Let $n = 10^6.$ Let $A \in \mathbb{R}^{n\times n} $ be the lower triangular matrix having 1's on and below the main diagonal.
We want to solve the following linear system:
$$ (A + uv^T)x = b$$
by the ...
3
votes
0answers
81 views
Compute Nullspace of Sparse Matrix
I am computing the nullspace of a sparse rectangular $m$ x $n$ matrix $A$, where $m$ << $n$. I do this by computing the QR decomposition of $A^T$ and extract the $n-m$ right-most columns of the ...
3
votes
0answers
36 views
Numerical calculation of the Berry connection
I'm doing some numerical calculations involving Hermitian matrices, and derivatives of the eigenvectors.
Essentially, I have an n x n, Hermitian matrix H(x), which is dependent on some continuous ...
3
votes
0answers
82 views
Is the matrix exponential and the Jordan canonical form actually useful for solving differential equations?
All of my yearlong graduate-level Linear Algebra course notes from my professor—an algebraist/representation theorist—shows his love for the exponential map $e^A$ and the Jordan canonical form—and one ...
5
votes
1answer
88 views
Accurately Computing a Positive Vector in the Nullspace of a Matrix
I'm sure this question has been asked before yet after many hours of searching I am unable to find a definitive answer.
The problem at hand is solving the linear system: $$A \mathbf{x} = \mathbf{0}$$ ...
0
votes
0answers
74 views
A parallelized GMRES solver?
My application calls for solving a dense, 40,000 x 40,000, ill-conditioned linear system. The native SciPy GMRES solver with preconditioning has worked well for my application and solving a single ...
2
votes
0answers
65 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 ...
1
vote
1answer
146 views
Is LAPACK behind the cutting edge of dense linear algebra?
I have been digging into some numerical linear algebra lately, and reading in particular about how LAPACK solves symmetric eigenvalue problems. I noticed that the ...
1
vote
2answers
188 views
Why OpenFOAM uses its own data structures and linear solvers?
I wonder why OpenFOAM code has its own data structures Lists, HashTables, ... etc. when there is the STL in C++?
Another ...
2
votes
1answer
72 views
Parallel, matrix-free estimate of the trace
What would be the best way to estimate the trace of a large, distributed matrix, if one only know its action on a vector throug a parallel "matvec" routine?
In the application I am interested in, the ...
1
vote
0answers
39 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 $...
0
votes
0answers
40 views
Spurious eigenvalues in a finite element eigenvalue problem
This post is closely related to this one and uses the exact same setup: a mix of quadratic and cubic basis functions in a finite element approach, where variables $u_1$ and $u_2$ are quadratic and $...
2
votes
1answer
136 views
Boundary conditions in a finite element eigenvalue problem
I've been reading multiple papers and related posts for a while now, but I can't seem to find a specific answer to the issues I'm having so I hope someone can clarify things here.
I'll provide some ...
3
votes
1answer
134 views
Implementation of a $O(n \log(n))$ method to compute eigenvalues of real symmetric tridiagonal matrices
I just came upon this paper, which details the implementation of a fast method to get eigenvalues of tridiagonal symmetric matrices :
Coakley, Ed S.; Rokhlin, Vladimir, A fast divide-and-conquer ...
1
vote
1answer
71 views
Solving triangular matrix equations on a GPU
Suppose I have these two $N\times N$ lower triangular banded matrices:
$A = \begin{bmatrix}
a_0 & & \\
a_1 & a_0 & \\
a_2 & a_1 & a_0 \\
a_3 & a_2 & a_1 & a_0 \\
&...
0
votes
1answer
28 views
Norm of operator in finite element discretization of Heat equation
I am solving the heat equation discretized spatially via FEM and temporally via backward Euler.
I get the system
$$M \dot{u} = K u +f$$ where $u$ is a vector representing the solution at spatial ...
1
vote
0answers
31 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 ...
3
votes
0answers
61 views
Fastest matrix library for Android (with GPU is possible)
I was working on an Android app that requires some linear algebra with matrices. The matrices will be somewhat medium-sized as they are not too small or too big. I was originally using jBlas because ...
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 ...
0
votes
0answers
87 views
Is there a subfield within computational science research that's done on pencil and paper?
Is there an area of computational science research that can be done on pencil and paper (with results written up for a journal format later on)?
I'm wondering if there is abstract proof-based linear ...
-1
votes
1answer
47 views
Find mass matrix in a system of linear equations
Given $z_t=\sum_{i=1}^t \theta_iz_{t-i}+v_t $, where $t=1,...,N$ where $N=1024$. I need to write this in matrix form (a system of linear equations) as $\mathsf{A}\mathsf{z} = \mathsf{z} - \mathsf{v}$. ...
1
vote
1answer
65 views
Flops of the computation of symmetric matrix $A$ to the power of $p$
What is the cost in terms of flops for the computation of $A$ to the power of $p$, where $p$ is a positive integer and $A \in \mathbb R^{n\times n}$ is a symmetric matrix?
3
votes
3answers
226 views
Using matrix exponential to solve linear system
Consider the system of linear equations:
$$
Ax=b
\tag{1}
\label{eq1}
$$
where
$A\in\mathbb F^{n\times n}$, diagonalizable dense matrix, over the field $\mathbb F$ of real or complex numbers,
$x\...
-1
votes
1answer
58 views
How to solve system of equations with almost-zero determinant?
I have a system of equations that I am trying to solve. In matrix form, it's written as
$$x(I - S) = b.$$
I am solving for $x$, where $I$ is the identity matrix and $S$ is a matrix where each column ...
0
votes
1answer
74 views
Desmos saying there are too many variables [closed]
I wasn't sure if this is a Computational Science SE question or a Stack Overflow question but I think it's more of this one.
I wanted to make a graph where I can rotate a hyperbola (not parabola or ...
2
votes
3answers
179 views
Generating Random Orthogonal Matrices in C++
I'm looking for an open-source library for the generation of random n-dimensional orthogonal matrices in C++.
In python, it looks like such a function is available in the NumPy package. But I was not ...
2
votes
1answer
114 views
Sparse matrix-matrix multiplication using AVX2
I have two sparse general matrices stored in CSR format I need to multiply. Is there any chance to gain performance using AVX2? In general the matrices are big (hundreds of millions of non-zeros and ...
-1
votes
1answer
103 views
How to implement the Hessenberg QR Algorithm?
For context, I'm creating a linear algebra library from scratch for learning purposes in C. Right now I'm working on calculating eigenvalues but my implementation of the QR Algorithm is diverging. ...
9
votes
1answer
2k views
Increasing computational performance by using 16 bit numbers
I recently found the following article where it was stated that using 16 bit numbers can be used to increase the computational performance of AI applications. According to the article numbers above 16 ...
0
votes
2answers
75 views
Update for QR factorization least squares
I found after some research that the most numerically stable way to solve the least squares problem is through QR factorization. For $n$ number of observations and $p$ number of parameters it takes ...
3
votes
2answers
224 views
Cholesky decomposition vs LDL decomposition
In different books and on Wikipedia, you can see mentions of Cholesky decomposition and only sometimes of LDL decomposition.
As far as I understand, LDL decomposition can be applied to a broader ...
3
votes
1answer
82 views
Big Theta Complexity of Gaussian Elimination using Complete Pivoting
I already know the Big O for partial pivoting is $O(n^3)$ and remain the same for complete pivoting. I also know the big theta complexity for partial pivoting is $2/3 n^3$
I would like to know the ...
2
votes
0answers
70 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 ...
3
votes
1answer
40 views
Nonlinear least squares resolution matrix
For a linear least squares problem, it is possible to define a resolution matrix, relating the estimated model parameters to the true model parameters. If we are solving a regularized problem,
$$
\...
4
votes
0answers
132 views
Explanation of subspace strategy regarding CG described in Golub's book
I was wondering about the last paragraph in Matrix Computations (4th edition) by Golub, Chapter 11 (11.3.3), specifically his explanation of subspace strategy for Conjugate Gradient.
Note that in ...
1
vote
2answers
79 views
Why Householder transformation can not be chosen to be an identity matrix?
For Householder transformation, we know that
$H = I-uu^T$, where $\|u\|_2=\sqrt{2}$. When it acts on any vector $x$, $Hx$ and $x$ is symmetric with respect to $span(u)^T$. But I have read a ...
3
votes
1answer
566 views
Efficient ways to numerically evaluate matrix exponentials
What are some computationally efficient ways to solve matrix exponentials, i.e. functions of the form :
$f(X)=e^{X}$, where $X$ is a square matrix?
So far I have been able to diagonalise some ...
1
vote
1answer
35 views
Determinant of a matrix after removing or adding lines and columns
In quantum mechanics, the wavefunction of N electrons is given by a determinant. I am working on a Monte Carlo algorithm. At each Monte Carlo step, I need to add or remove an electron, which means ...
2
votes
2answers
234 views
Inverting really big symmetric block diagonal matrix
I have a really big symmetric 7.000.000 X 7.000.000 matrix that i would like to invert. The matrix is extremely sparse and it can be rearranged as to become a block diagonal matrix. The biggest blocks ...
33
votes
2answers
12k views
why is A*v+B*v faster than (A+B)*v?
$A$ and $B$ are $n \times n$ matrices and $v$ is a vector with $n$ elements. $Av$ has $\approx 2n^2$ flops and $A+B$ has $n^2$ flops. Following this logic, $(A+B)v$ should be faster than $Av+Bv$.
Yet,...
1
vote
0answers
58 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 ...
2
votes
1answer
59 views
Solution method of nonlinear heat transfer analysis
The governing equation of transient heat transfer analysis is described as follows:
$$C \frac{dT}{dt}+K T = Q$$
When using backward difference scheme for the discretization of the time we get the ...
4
votes
0answers
89 views
Trying to understand splitting-based iterative method for 2D Laplace problem
I am trying to understand the theory behind a splitting based iterative method which uses the incomplete Cholesky factorization. Before giving the specific details, let me first give the problem ...
