Questions tagged [numerical-linear-algebra]

{numerical-linear-algebra} questions involving algorithms for linear algebra computations.

Filter by
Sorted by
Tagged with
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. ...
Watson Ladd's user avatar
  • 2,419
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})$,...
Ralph B.'s user avatar
  • 135
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 $...
Saheb's user avatar
  • 21
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 ...
SIM2's user avatar
  • 73
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 ...
Saurabh Agrawal's user avatar
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$ ...
wfe2016's user avatar
  • 21
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 ...
Doron Shafrir's user avatar
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....
D. Rusin's user avatar
  • 381
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 ...
user avatar
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 \...
Yauhen Yakimenka's user avatar
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. ...
yon's user avatar
  • 303
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}\...
drszdrsz's user avatar
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{...
yarchik's user avatar
  • 482
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 ...
Astor's user avatar
  • 323
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 ...
Astor's user avatar
  • 323
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 & \\ \...
vkonton's user avatar
  • 175
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 $...
B. Arsic's user avatar
  • 123
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_{...
nimamura's user avatar
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 $\...
Nikolayevich's user avatar
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, ...
berkin's user avatar
  • 41
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 ...
glwhart's user avatar
  • 161
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 ...
cangrejo's user avatar
  • 161
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 ...
le4m's user avatar
  • 183
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_{...
Hamed's user avatar
  • 105
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 ...
user2813942's user avatar
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) ||...
Learning math's user avatar
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 $...
Supriyo's user avatar
  • 343
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 ...
Alec Jacobson's user avatar
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 ...
kfeng123's user avatar
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: \...
ashok's user avatar
  • 31
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}+\...
Daeyoung's user avatar
  • 133
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}^{...
user avatar
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 ...
Tom Steiglitz's user avatar
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 ...
Moonwalker's user avatar
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 ...
J. Doe's user avatar
  • 31
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 ...
maomao's user avatar
  • 492
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 ...
Joe's user avatar
  • 31
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 ...
Marc's user avatar
  • 23
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 ...
FaCoffee's user avatar
  • 241
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 ...
user91322's user avatar
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 ...
Creator's user avatar
  • 435
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....
h2020's user avatar
  • 11
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$ ...
Simd's user avatar
  • 3,195
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 ...
Ulderique Demoitre's user avatar
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 ...
Alex Flint's user avatar
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}$. ...
qbit-'s user avatar
  • 71
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 ...
fnd's user avatar
  • 3
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(\...
Jason S's user avatar
  • 653
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 ...
Federico Poloni's user avatar
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 ...
lino's user avatar
  • 253