Questions tagged [numerical-linear-algebra]
{numerical-linear-algebra} questions involving algorithms for linear algebra computations.
289
questions
5
votes
1
answer
1k
views
Solving a system of linear equations over the integers
I have a matrix with integral entries $A$ and integer vector $b$, and want to determine if there is exactly one vector $x$ such that $Ax=b$. $A$ is rectangular, and I know there always is a solution.
...
3
votes
1
answer
286
views
Numerical iterative methods for Poisson equation
Given a domain $\Omega \subset \Bbb R^n$ and $\Delta\varphi=f$ where $\varphi:\Bbb R^n \to \Bbb R$ is unknown and $f:\Omega\to \Bbb R$ is a blackbox function (for each $\bf x$ it provides $f({\bf x})$,...
2
votes
1
answer
133
views
Quadratic matrix equation for $X\in \mathbb{C}^{ n\times p}$ with Hermitian parameters
Let $A\in \mathbb{C}^{ n\times n}$ and $B \in \mathbb{C}^{p \times p}$ be Hermitian matrices with $p < n$.
Find matrix $X$ such that $X^*AX=B.$
Solution in the case of positive definite $A$ and $...
7
votes
3
answers
1k
views
Checking positive semi-definiteness of integer matrix
Key Problem : Is there any theorem about eigenvalues or positive semi-definiteness of small size matrices with small integer elements?
I have to check positive semi-definiteness of many symmetric ...
1
vote
0
answers
18
views
Empirical approaches to validate observational bounds on minimum gap between least eigenvalues of $n \times n$ correlation matrix and its submatrices
Let
$\Sigma$ be an $n \times n$ correlation matrix whose least eigenvalue is denoted by $\lambda$.
$\Sigma_i'$ be an $(n-1) \times (n-1)$ submatrix of $\Sigma$ obtained by eliminating the $i$-th row ...
2
votes
0
answers
43
views
Partitioning $n$-space based on linear combinations
I'm trying to figure out the approximate number of areas the positive $n$-space will be divided into if we partition it as follows: we have $k$ linear functions $F_1$, $F_2$, ..., $F_k$ on $n$ ...
7
votes
2
answers
516
views
Linear equations with absolute values
Assume we have a set of equations in $x \in \mathbb{R}^n$
$$|a_i\cdot x|=b_i$$
where $a_i \in \mathbb{R}^n$ and $b_i>0$ are given.
Could such a system be solved efficiently?
In a theoretical ...
4
votes
0
answers
500
views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
5
votes
1
answer
1k
views
In a large sparse matrix, how many eigenvalues/eigenvectors are “spurious”?
In a large (possibly above $5000\times 5000$) matrix, the problem of finding all the eigenvalues and eigenvectors can be solved using iterative methods (Arnoldi, Lanczos etc.). However, there seems to ...
4
votes
0
answers
923
views
Generate non-negative linear combinations of non-negative vectors with different supports
(I will not be surprised if this problem has been solved and/or has a trivial solution – I just do not know the right terminology to google for it.)
So the problem is as follows. I have an $m \...
1
vote
0
answers
113
views
smallest singular value over invertible sub-matrices
Consider the matrix $M = \begin{bmatrix} A & A B \end{bmatrix} \in R^{n \times (n+m)}$, with $A \in R^{n\times n}$, $B \in R^{n \times m}$, $m < n$, $m > 1$, $A$ symmetric positive definite.
...
1
vote
1
answer
386
views
Laplace equation, medium discontinuity and finite difference method
The main question is: How to deal with the Poisson equation in the presence of the medium interface.
Let's say we have 1D Laplace equation:
\begin{equation}
-\frac{d}{dx}\left(\epsilon(x)\frac{d}{dx}\...
7
votes
0
answers
188
views
A special eigenvalue problem
For my research I need to solve a generalised eigenvalue problem
$Ax=\lambda B x$, where $A$, $B$ are general matrices, and selectively find only eigen-pairs $\lambda, x$ such that $\lambda\in \mathbb{...
2
votes
0
answers
112
views
Coarse grid correction
Let $A_h \in \mathbb{R}^{n \times n}$ be the matrix corresponding to a finite element discretization of some nonselfadjoint, bounded and indefinite bilinear form corresponding to a second order ...
4
votes
0
answers
143
views
Zero diagonal nonsymmetric block checkerboard matrix: orbits and numerical ranges
Let $A \in \mathbb{R}^{m \times m}$ be a nonsymmetric zero diagonal matrix with a zero/non-zero pattern which is symmetric and persymmetric (i.e. symmetric in the northeast-to-southwest diagonal).
If ...
1
vote
1
answer
148
views
Solving Linear System with Noisy Input
I have the following triangular system
\begin{equation}
\begin{pmatrix}
1 & & & & \\
\mu_1 & 2 & & & \\
\mu_2 & \mu_1 & 3 & \\
\...
4
votes
0
answers
2k
views
What is the time complexity of the largest singular value and its vectors?
Full zero-error SVD on an $m \times n$ matrix $A$ would cost $O(\min(m^2n,mn^2))$. What is the time complexity if we need only the largest singular value and its corresponding vectors? I think it is $...
3
votes
2
answers
832
views
Numerically solving for pseudo inverse of non-squared Vandermonde matrix
I have a linear system to solve, set up as:
$\bf{Ax}=\bf{b}$
with a non-squared matrix A,
$
\bf{A}=
\begin{bmatrix}
1 & A_{1} & A_{1}^2 & \cdots & A_{1}^n \\
1 & A_{2} & A_{...
2
votes
1
answer
4k
views
Is the square root of a matrix unique? [closed]
I know the answer is No, since you can put plus/minus on each eigenvalue. But how about putting a psd requirement? Like $A = S^2$, $S$ is psd, is $S$ unique?
I was worried about the case where if $\...
4
votes
0
answers
560
views
Determining whether a Schur complement is invertible
Consider the symmetric matrix
$$M = \begin{bmatrix}
A & B \\
B^T & -C
\end{bmatrix}$$
where $A \in \cal{R}^{n \times n}$ and $C \in \cal{R}^{m\times m}$ are symmetric, ...
1
vote
0
answers
966
views
Condition number of the product of two matrices
Consider two matrices $A$ and $B$ that are non-square in general and may not be full rank. Assuming their shapes are such that the product $A\cdot B$ is well-defined, what is the relationship between ...
4
votes
2
answers
1k
views
Lower bounds for the singular values of submatrices of othogonal matrices
Let $A$ be an $m \times n$ matrix, $m\geq n$, and let $A=U\Sigma V^T$ be its singular value decomposition.
Let us partition $A$ as $A=(A_1|A_2)$, where $A_1$ is of size $m \times k$, and all columns ...
1
vote
1
answer
136
views
error bound for least square minimization
Let $X = [x_1 \cdots x_N] \in \mathbb{R}^{d \times N}$ and $ T= [t_1 \cdots t_N] \in \mathbb{R}^{1 \times N}$. Define
$$
E(w) = \text{tr}(T - w^TX)(T - w^TX)^T
$$
as least square energy. When ...
0
votes
1
answer
110
views
How to show inconsistency of a linear system of equations? [closed]
Consider the (real) linear system of equations $A\mathbf{x}=\mathbf{c}$ of size $N$ as
$$
\begin{bmatrix} a_{N}-a_{2}& a_{2}& 0 &\dots& 0 & -a_{N} \\-a_{1} & a_{1}-a_{3}&a_{...
3
votes
2
answers
263
views
Question about preconditioning
I posted the following question on stackexchange but didn't get any replies; I'm hoping perhaps someone can help me here.
I understand that for many iterative methods, convergence rates can be shown ...
4
votes
3
answers
2k
views
Is this inequality involving the Frobenius norm right?
Let $A$ be a generic (or varying) square, real $ n \times n$ matrix. Let $G$ be a fixed $n \times k$ matrix, $k < n.$ Denote by $||.||_F$ the Frobenius norm.
Is it true that $||AG||_F \geq c(G) ||...
8
votes
1
answer
462
views
When are two binary matrices simultaneously equivalent to their transpose?
For any real square matrix $A$ there is an invertible matrix $P$ such that $A^t = P^{-1}AP$. I have two binary ($0,1$) matrices $A$ and $B$. When does there exist a $P$ such that $A^t = P^{-1}AP$ and $...
11
votes
2
answers
4k
views
How can one construct a sparse null space basis using recursive LU decomposition?
Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
4
votes
1
answer
393
views
minimizing the product of rayleigh quotient
The problem is:
$$\min_{\alpha}\frac{\alpha^T A \alpha}{\alpha^T\alpha}\frac{ \alpha^T B \alpha}{\alpha^T\alpha}$$
where $A$ and $B$ are symmetric and positive definite matrix.
I think the explicit ...
3
votes
1
answer
603
views
Properties of one dimensional null space
Let $\mathcal{G}$ be denote the set of all $3 \times 3$ real symmetric matrices and let $\mathcal{G}^+$ denote the set of all $3 \times 3$ positive semidefinite matrices (see definition).
Let $S: \...
3
votes
2
answers
2k
views
Matrix equation with Hadamard product and its own inverse involved
I know there is an almost exactly same question here but I have further specifications. So my problem is as follows:
$$
\Omega^{-1}=\dfrac{1}{n}\left(\Omega\odot \mathbf{W}+\mathbf{X}'\mathbf{X}+\...
0
votes
1
answer
562
views
Recurrence Equation and Matrix Convergence
To begin with, let us give the conceptual background needed to expose the problem. First of all, we shall consider the set $\mathbb{L}^{n} = \mathbb{R}^{n}_{\geq0} = \{\overrightarrow{x}\in\mathbb{R}^{...
2
votes
0
answers
258
views
Difficult integral - speed up numerical integration using a trick?
I have the following integral that I need to solve (with high precision) millions of times in my simulations. This is time consuming and is prohibiting me from proceeding from proceeding forward.
I ...
4
votes
2
answers
626
views
Difference between Chebyshev first and second degree iterative methods
Consider linear equation $Au = f$.
We want to solve it with iterative method (assuming $A$ is good).
First order iterative method is:
$$
u^{k+1} = u^k - \alpha_{k+1}(Au^k - f),
$$
The second degree ...
2
votes
1
answer
233
views
Computing 3-term connection coefficients for wavelets
I am trying to calculate the three-term connection coefficients
$$
Λ_{l,m}^{d_1,d_2,d_3} = \int_{-\infty}^\infty \varphi^{(d_1)}(x) \varphi^{(d_2)}_l(x) \varphi^{(d_3)}_m(x) dx
$$
for Daubechies ...
1
vote
0
answers
167
views
Matrix exponential bounds
Let $A$ be a stochastic matrix, $q\in (0,1)$. How to bound $n$ such that $$q^n A^n e^A \leq e^A$$
Note that here $e^A$ is the matrix exponential, and $\leq$ is taken entrywise.
To be clear, what I ...
3
votes
1
answer
380
views
The spectral norm of the truncated exponential of a matrix
Let $A$ be a matrix satisfying $A^*+A\leq0$, it can be shown that $\|e^{tA}\|_2\leq1$ for all $t\geq 0$, where $\|\cdot\|_2$ is the spectral norm defined as largest singular value of the matrix.
I am ...
2
votes
1
answer
994
views
How to retrieve eigenvectors from shifted QR algorithm?
I understand that the key to retrieve eigenvectors in the non-shifted QR algorithm is to accumulate the transformations at each steps in the following way:
$Q = \Pi_i Q_i$
Can we accumulate the ...
12
votes
2
answers
8k
views
What is the time complexity of the matrix exponential?
While trying to compute the Matrix Exponential of an $n \times n$ array I decided to take advantage of a Python function called scipy.linalg.expm().
According to ...
4
votes
1
answer
405
views
Behaviour of eigenspaces of adjacency matrices after a single change to the graph
Say I know the eigenvalues and eigenvectors of an adjacency matrix of an unweighted graph. Can I say anything about the eigenvalues and eigenvectors of an adjacency matrix of a graph with one extra ...
8
votes
1
answer
1k
views
Finding Toeplitz matrix nearest to a given matrix
For an arbitrary $N\times N$ Hermitian matrix $A$, I want to derive a Toeplitz matrix from $A$ such that the eigenvectors of both matrices have minimal change.
Specifically I want find the Toeplitz ...
1
vote
0
answers
346
views
The application of recursive SVD [closed]
Given an n*m matrix A, the SVD decomposition of A is ${\rm SVD}(A)$= $USV^t$.
The application of SVD to the product of U and S gives as a result the same matrices multiplied by the identity matrix, i....
6
votes
2
answers
529
views
How to estimate a specific infinite matrix sum
Let $M$ be an $n$ by $n$ matrix with each diagonal element equal to $k$ and each non-diagonal element equal to $k-1$ where $n$ and $k$ are positive integers. Let $k < n$ and we can assume both $k$ ...
2
votes
0
answers
124
views
SVD when only off-diagonal terms are known
I have a real matrix $A \in \mathbb{R}^{n\times n}$ such that:
$A$ is symmetric
All the off-diagonal terms are known and positive
Has rank $k<n$
Unfortunately I don't know the values of the ...
0
votes
1
answer
453
views
Efficient computation of matrix exponential of trace zero matrix [closed]
I am looking for identities that may help with numerical computation of the matrix exponential ${\rm exp}(A)$ where ${\rm tr}(A)=0$. I am already aware of general-purpose algorithms for computing the ...
6
votes
1
answer
568
views
Tensor matricizations and their decompositions
Suppose we have a 4-index tensor $t_{ijkl}$ (all 4 dimensions are equal size). We can make a matrix out of it by taking first and last two indexes as new indexes: $t_{ijkl} \rightarrow M_{ij, kl}$. ...
0
votes
1
answer
149
views
Need help with computational and numerical methods for solve equations
This is my first question on this community. I am a applied scientist, not a mathematician.
I have the following simplified problem:
Let $u: [0,1] \rightarrow \mathbb{R}_+$ a real valued function ...
1
vote
1
answer
137
views
Similarity transform of a diagonalizable matrix that minimizes the Euclidean condition number
If I have a diagonalizable matrix $A = V\Lambda V^{-1}$, is there a way to show that for any similar $B$ such that $B = T\Lambda T^{-1}$, the Euclidean condition number $\kappa_2(B) \geq \kappa_2(\...
7
votes
1
answer
231
views
Add a multiple of $I$ to a matrix to minimize its operator norm
Given $A\in\mathbb{C}^{n\times n}$, what is $s_* = \arg\min \|A-sI\|$?
Here $\|A\|$ is the operator norm, $\|A\|=\rho(A^*A)^{1/2}$, and $I$ is the identity.
The corresponding problem for the ...
12
votes
2
answers
4k
views
Why Householder reflection is better than Givens rotation in dense linear algebra?
It’s obvious that Givens rotation works better with sparse matrices. But I don’t know why Householder reflection is better for dense matrices. Does it require less computations? Or it’s numerically ...