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.
1,124
questions
3
votes
1
answer
116
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
0
answers
47
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,048
3
votes
1
answer
642
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 ...
- 33
3
votes
1
answer
397
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 ...
- 153
1
vote
1
answer
316
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 \\
&...
- 791
1
vote
1
answer
81
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 ...
- 155
1
vote
0
answers
49
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 ...
- 11
4
votes
0
answers
543
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
0
answers
52
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 ...
- 792
0
votes
0
answers
95
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
1
answer
118
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}$. ...
- 101
1
vote
1
answer
100
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
3
answers
538
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\...
- 8,602
-1
votes
2
answers
545
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 ...
- 119
0
votes
1
answer
3k
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 ...
- 103
2
votes
3
answers
976
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
1
answer
352
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 ...
- 840
0
votes
1
answer
1k
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
1
answer
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 ...
- 840
0
votes
2
answers
680
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 ...
- 356
4
votes
2
answers
3k
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 ...
- 356
3
votes
1
answer
189
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 ...
- 33
2
votes
0
answers
109
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 ...
- 129
3
votes
1
answer
77
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,
$$
\...
- 1,048
5
votes
0
answers
144
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 ...
- 161
1
vote
2
answers
386
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 ...
- 961
4
votes
1
answer
3k
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
1
answer
49
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 ...
- 143
3
votes
2
answers
1k
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 ...
- 31
37
votes
2
answers
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,...
- 525
1
vote
0
answers
87
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 ...
- 19
2
votes
1
answer
314
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 ...
- 840
5
votes
0
answers
97
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 ...
- 51
2
votes
0
answers
71
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 ...
- 840
5
votes
0
answers
130
views
Levinson Recursion for Non Square Toeplitz Matrices
Given a rectangular Toeplitz Matrix $ H $, how could one solve:
$$ y = H x $$
For instance, $ H $ can be Linear Convolution Matrix of the filter $ h $:
$$ H = \begin{bmatrix}
{h}_{1} & 0 & ...
- 332
1
vote
0
answers
79
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–...
- 21
5
votes
1
answer
673
views
Fastest way to calculate the $2$-norm (or an upper bound for the $2$-norm) of the inverse of a matrix $A\in \mathbb{C}^{N\times N}$
I have a matrix $A\in \mathbb{C}^{N\times N}$ and I need to calculate $||A^{-1}||_{2}$ efficiently. Can it be done without having to evaluate the inverse explicitly?
In general, I am looking for ...
- 153
2
votes
0
answers
58
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 ...
- 141
10
votes
3
answers
633
views
Linear algebraic research direction that's not to do with differential equations and physics?
So I've found some interesting linear algebraic research areas that's both pure-ish, with a numerical bent to it, too -- e.g. inverse eigenvalue problems have both interesting theoretical and ...
- 101
5
votes
0
answers
87
views
Nonlinear least squares optimized Jacobian calculation
I have a nonlinear least squares problem, in which I am trying to minimize residuals which can be divided into four classes:
$$
\min_x ||\epsilon(x)||^2 + ||\xi(x)||^2 + ||\delta(x)||^2 + ||s(x)||^2
$$...
- 1,048
4
votes
3
answers
224
views
Solving for a vector in a linear system that is both left and right multiplied
I have a linear system where I am given 2 matrices, $A$ and $B$, and 2 vectors, $v$ and $c$, and I need to solve for the vector $x$. $A$ is $n\times n$, $B$ is $n \times n \times n$, and the vectors $...
- 2,069
3
votes
0
answers
361
views
What is the fastest algorithm for computing log determinant of a PSD matrix? (All possible PSD matrices)
I am diving into some literature to understand which is the best algorithm for computing the log-determinant of a PSD matrix. More generally, I am interested in a list of resources to read, which ...
- 131
4
votes
1
answer
97
views
Is operation count a reliable predictor of performance when comparing two formulations?
I have two formulations to solve a problem (both give dense, complex and symmetric system). They are solved multiple times in a loop. I am trying to predict which is better to use.
The first one ...
3
votes
0
answers
47
views
Subspaces for Iterative methods
In the original paper of Conjugate Gradients, the authors mention that if we pick the canonical basis $\{e_1,e_2,\ldots,e_n\}$, to obtain A-orthonormal vectors, we end up with the Gaussian elimination ...
- 171
1
vote
1
answer
402
views
Spline regularization
I am fitting some B-splines to data, but the data has a "gap" region where the spline is less constrained by the data. I want to devise a regularization scheme to help prevent the spline from ...
- 1,048
0
votes
1
answer
168
views
Method to calculate solution of a linear equation system?
I am searching a solution method for the following equation system of equation systems:
Let $A, B \in \mathbb{R}^{n \times n}$ be s.p.d. Matrices and $O$ be the zero matrix of the same size. Further ...
user29088
1
vote
1
answer
2k
views
Solve linear system with Newton-Raphson method
Is it possible to solve a linear matrix system $A x = b$ using the Newton-Raphson method? If yes, how can this be done? More special, how is the derivative build?
- 840
4
votes
1
answer
379
views
Low rank update of QR of inverse
I am in a situation where as part of a sort of inverse power method scheme, I want to very often perform the following step:
Apply a symmetric rank one update $uu^\top$ to my inverse matrix $A^{-1}$
...
- 143
0
votes
1
answer
69
views
How to find the nearest point inside a list in a given direction
Being $\bar{\mathbf{x}} \in \mathbb{R}^3$ a point and $S =\{\mathbf{x}\}_{i=1}^N \in \mathbb{R}^3$ a sample of N points. I am looking for a simple algorithm to determine the nearest point in $S$ in ...
- 139
0
votes
1
answer
82
views
Analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^T A z$, where $A=uu^T+vv^T$
Let $u$ and $v$ be column vectors of size $n \gg 1$ (not both zero), and consider the matrix $A:=uu^T+vv^T$
Question
What is an analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^TAz=\arg\max_{\|z\...
- 165