Questions tagged [numerical-linear-algebra]
Questions on the various algorithms used in linear algebra computations (matrix computations).
3,452
questions
2
votes
0
answers
39
views
LU decomposition of banded matrix with partial pivoting
Disclaimer: I'm rusty as can be in this department.
I'm looking into how to implement a banded matrix LU decomposition with partial pivoting ($PA = LU$). So to start with I implemented regular matrix ...
- 123
0
votes
0
answers
13
views
Derive conditional number for eigenvalue [closed]
How to derive the absolute conditional number,
$$\kappa \le \frac{\|x\|_2\|y\|_2}{|y^*x|}$$
where x is the right eigen vector of matrix A and y is the left eigenvector.
I tried to perturbed the system ...
0
votes
0
answers
31
views
Product between matrix-polynomial and vector
I was wondering if it is possible to optimize the evalutaion of the product of a matrix polynomial and a vector.
$$ \vec{y} = \left( \sum_{i=0}^{n}a_iM^i \right)\vec{x}$$
Matrix size is maybe ...
- 31
0
votes
0
answers
33
views
Prove an equation about Frobenius norm
The problem:
Show that if $\textbf{0} \neq \textbf{v} \in \mathbb{R}^{n}$ and $E \in \mathbb{R}^{n\times n}$, then
$$\Big\lVert E(I - \frac{\textbf{v}\textbf{v}^{T}}{\textbf{v}^{T}\textbf{v}})\Big\...
- 13
0
votes
0
answers
36
views
How to approximately diagonalize a special symmetric hermitian matrix?
Given a hermitian matrix $H$ as follows:
\begin{equation}
H =
\begin{bmatrix}
H^1 & V^{12} \\
V^{21} & H^2
\end{bmatrix}.
\end{equation}
Here, $H^1,H^2\in\mathbb{C}^{N\times N}$ ...
- 1
-1
votes
0
answers
31
views
Second differnce fixed-fixed matrices to approximate u''
This is a question that's been stumping me for a while.
Here's my attempt: Since they asked us to use K3, n = 3 and hence the mesh width h = 1/4 as h = 1/(n+1)
Now we construct the 3x3 K3 matrix and ...
1
vote
1
answer
49
views
The spectral radius analysis
This is a question from numerical linear algebra. It originates from iteration method: Suppose $Ax = b$, we split $A = A_1+A_2$, then $A_1x = -A_2x+b$, if $A_1$ is invertible, then $x = -A_{1}^{-1}A_2 ...
- 189
0
votes
0
answers
9
views
Which row/column to remove from SPD matrix to remain maximal volume
Let $A$ be a real $N\times N$ symmetric, positive definite (SPD) matrix with volume $vol(A)=|det(A)|$. Let $B_i$ be the matrix $A$ where row and column $i$ were exchanged by a unit vector $e_i$. Can I ...
- 1
2
votes
0
answers
15
views
Finding a mapping from the hypercube to a convex hull that conserves the uniform distribution
I am drawing points uniformly in a hypercube $x \in [-1,1]^n$ and I would like to find a map f(x) = y such that $||y||_1 \leq 1$ and that the uniform distribution is conserved.
My own attempt at this ...
- 35
1
vote
0
answers
20
views
Computational limits for nonlinear solver accuracy
Recently I've been curious about the following question. Suppose that $f:\mathbb{R}^n\rightarrow \mathbb{R}$ is a nonlinear convex function and we seek to minimize it by Newton's method. That is we ...
- 2,080
0
votes
1
answer
36
views
Writing a Givens Matrix as a Product of At Most Two Householder Transformations?
Is there a way of proving that any givens matrix is a product of at most two householder matrices?
Here is what I have tried so far:
I can see why this holds in two dimensions because any householder ...
- 399
0
votes
0
answers
22
views
Cholesky Decomposition of sum of matrix
Consider a positive definite matrix $A=B+C$, where $B$ and $C$ are both semi-positive definite and $Im(C)=Im(B)^{\perp}$. If $A$ has a Cholesky decomposition $A=LL^{T}$, then whether the matrix $L$ ...
- 315
0
votes
0
answers
12
views
Relation between singular value, eigen value and 2-norm
I am confused.
We have that,
$ \sigma_{max} \ge \rho(A) = \|A\|_2$.
where $ \rho(A) = |\lambda_{max}|$ and $\sigma$ is the singular value of A.
And, $\sigma^2 = \lambda(A^*A)$.
But, $\rho(A) \ne \sqrt{...
user1220545
0
votes
2
answers
37
views
2-norm of transpose proof
I don't understand the proof of ‖x‖2=‖xT‖2.
I know you can use the Cauchy-Schwartz inequality and that you can prove it by first showing ‖xT‖2 ⩽ ‖x‖2 and then ‖x‖2 ⩽ ‖xT‖2. I get proving both ...
- 11
1
vote
0
answers
26
views
Recommendations for Papers on LLL Algorithm
Asked a professor who does research in cryptography for a project opportunity, and he told me to go read about Lenstra-Lenstra-Lovasz or LLL algorithm. I read the following paper and found the topic ...
0
votes
0
answers
17
views
Relation between F-norm and 2-norm
From the definition of 2-norm, $\||A|\|_2 = sup_{\|x\|_2 = 1} \||A|x\|_2$.
Since F-norm is equal to 2-norm of vector we have that, $\||A|\|_2 = sup_{\|x\|_2 = 1} \||A|x\|_2 = sup_{\|x\|_F = 1} \||A|x\|...
user1220545
1
vote
1
answer
23
views
Relation between 2-norm and F-norm
$\|A\|_2 = \sup_{\|x\|_2 = 1} \|Ax\|_2 = \sup_{\|x\|_2 = 1} \|Ax\|_F$
since A is a matrix and x is a vector, then $Ax$ is a vector.
And we have that $\|x\|_2 = \|x\|_F$, right?
user1220545
0
votes
1
answer
38
views
Matrix norm identity. Understanding inequallity.
Let A $\in R^{m\times n}$. What dose it mean when the book then write A : $R^{n} \rightarrow R^{m}$?
I try to understand this inequality:
$\frac{1}{\sqrt m} \|\mathbf{A}\|_1 \le \|\mathbf{A}\|_2 \le \...
user1220545
2
votes
1
answer
71
views
Matrices that are simultaneously Cauchy matrices and Toeplitz ones
The article
https://www.sciencedirect.com/science/article/pii/002437959190321M
defines "Cauchy-Toeplitz matrices" those matrices that are simultaneously Cauchy matrices and
Toeplitz ones.
...
- 23
0
votes
0
answers
14
views
How can I "compress" a known homogenous coordinate affine transformation?
Having worked with geometry I am aware of homogenous coordinates and affine transformations. With linear algebra we can express it as
$$\begin{bmatrix}x_1\\1\end{bmatrix} = \begin{bmatrix}R&T\\0&...
- 25.4k
1
vote
0
answers
49
views
Solution to 4x4 system of linear ODEs: what do the eigenvectors and eigenvalues represent and the solution to the ODE?
I have the following system of homogeneous linear differential equations that I wish to solve:
$$
\textbf{M}\ddot{\textbf{q}} + \textbf{G}\dot{\textbf{q}} + \textbf{D}\dot{\textbf{q}} + \textbf{K}\...
0
votes
0
answers
13
views
Truncated QR decomposition update (column deletion):
Suppose we begin with a matrix V and create a new matrix L by appending A*V and V as columns, i.e., $$L = [AV, V],$$where A has dimensions (N,N), and V of dim (N,r).
Afterward, we perform a truncated ...
0
votes
0
answers
20
views
How to formulate nuclear norm minimisation (of a matrix) as an SDP?
It is pretty well-known that the minimisation of the nuclear norm (sum of all singular values) is closely related to semidefinite programming.
However, I struggle to find a way to rewrite the problem &...
- 7,071
0
votes
1
answer
71
views
Found Eigenvector is close to the solution but not correct, what step am I missing?
While practicing finding eigenvectors I have this matrix A:
\begin{bmatrix}
9 & 0\\
0 & 4
\end{bmatrix}
The eigenvalues I found are $\lambda = 9,4$
(A) In finding the corresponding eigenvector ...
1
vote
0
answers
30
views
Efficient inversion of Cholesky decomposed matrix
I'm programming a machine learning model in C#, using the MathNet.Numerics library. As a part of this I am writing a class that models a distribution parameterized by a positive definite matrix $M$. ...
- 391
0
votes
0
answers
33
views
Finding amount of repetitions to achieve an error in Jacobi's method
I have a question about a problem that am trying to solve. I am given matrix
$$
A=\begin{pmatrix}2 & -1 & 0\\-1 & 2 & -1\\0&-1&2\end{pmatrix},
$$ and matrix
$$B=\begin{pmatrix}...
1
vote
1
answer
37
views
Building a preconditioned iterative method
Consider a preconditioned iterative method of least residuals for solving a system of linear equations $Ax=b$ with positive definite matrix $A$:
$$
\tag{1}
r_n = b - A x_n; \\
\alpha_n = \frac{(A M^{-...
- 141
3
votes
1
answer
173
views
What unique value does Cramer's rule offer?
When I was studying linear algebra, the textbook first taught Gaussian elimination and then introduced Cramer's rule. Great, I learned two methods for solving systems of linear equations. However, ...
- 51
0
votes
3
answers
55
views
Matrix operation to count nonzero elements
I require a function to count the nonzero elements in an integer-valued matrix $A\in \mathbb {N}^{n\times n}$.
I am aware that the standard approach would be to define a binary matrix $B\in\{0,1\}^{n\...
- 13
1
vote
0
answers
19
views
Optimal Choice of Regression points for Minimizing the Approximation Error when solving a PDE with Function Approximation
I want to solve a high-dimensional PDE $F(\mathbf{x}, v ,\triangledown v , \triangledown^2 v )$
$$
-\dot{V_{t}}(\mathbf{x}) - A (\triangledown v_t (\mathbf{x})) = f(\mathbf{x}) , \quad \mathbf{x} \...
- 41
0
votes
0
answers
29
views
Gauss-Seidel and bound of iterations using the residual norm
I would like to find the least $k\in \mathbb{N}$ such that $$Res=\frac{\|b-Ax^{(k)}\|}{\|b\|}\leq \epsilon$$ for given $\epsilon$, when using the Gauss-Seidel iteration. I calculated the norm (...
2
votes
1
answer
48
views
Using underdetermined system for dimensionality reduction.
I have an underdetermined linear system $A\vec{x} = \vec{b}$. I.e. A is $M$x$N$ and $M < N$.
Now, I want to be able to calculate $M$ of the values of $\vec{x}$ from the $N$-$M$ rest.
I know how to ...
- 31
1
vote
1
answer
19
views
Finding Matrix of Minimum 2-norm to obtain singular matrix
Let $A,X \in \mathbb{R}^{m \times m}$ with rank$(A) = m$. Find $X$ of minimum 2-norm for $A + X$ to be singular.
My thoughts:
Since we want $A + X$ to be singular, we want to show that it has a zero ...
0
votes
1
answer
22
views
Error on trace of quadratic forms from Frobenius error bound on central matrix
$\DeclareMathOperator{\Tr}{Tr}$
If a Frobenius error on an estimate of covariance $\|\tilde{\boldsymbol{M}}-\boldsymbol{M}\|_F$ is known to be in the order of $\tilde{O}(f(n,d))$ as some function of $...
- 191
1
vote
1
answer
70
views
Computing Smith normal form in $\mathbb{Z}/2\mathbb{Z}$ in Python [closed]
I am not sure if my question belongs here or more on stackoverflow as it concerns programming aspects of linear algebra. But I would like to compute the Smith normal form of a matrix $M$ with ...
- 23
0
votes
0
answers
13
views
Checking whether matrix is PD vs computing PD completion
Let $E$ be a subset of entries of a real symmetric $n \times n$ matrix. We want to find a positive-definite matrix $X$ such that $X_{i,j}=M_{i,j}$ for all $(i,j) \in E$ for a fixed positive ...
- 177
0
votes
1
answer
32
views
Rank deficiency in null space computation via SVD
Dear numerical algebra experts,
I am trying to find $\alpha$ for which $A(\alpha)x=0$ has a non-trivial solution ($x\neq0$), i.e. I am looking for $\alpha_0$ for which the null space of $A(\alpha_0)$ ...
0
votes
0
answers
30
views
Computationally efficient method for determining the complex norm of a vector times a diagonal matrix
I am trying to reproduce the algorithm from the paper: Kunis, S., & Potts, D. (2007). Stability results for scattered data interpolation by trigonometric polynomials. SIAM Journal on Scientific ...
- 71
0
votes
0
answers
53
views
Uniqueness of singular vectors (Theorem 4.1 Trefethen & Bau)
I am looking for some clarifications in the uniqueness portion of the proof of Theorem 4.1 of Trefethen & Bau's Numerical Linear Algebra.
The definition of the SVD and the proof exerpt from the ...
- 177
0
votes
1
answer
36
views
Linear matrix inequalities equivalent transformation trick
I am struggling to understand a proof regarding the transformation of matrix inequalities and need your help. Thank you in advance.
I am reading the following paper: https://arxiv.org/pdf/2304.03519....
0
votes
3
answers
53
views
Finding the bounds of the missing values of a symmetric positive semidefinite matrix
Suppose we have a symmetric matrix that we know is positive semi-definite and has missing entries. For example:
$
\begin{pmatrix}
1&1&1\\
1&1&x\\
1&x&1
\end{pmatrix}
$
How can ...
- 686
2
votes
0
answers
35
views
Achievable speedup of matrix-vector products with sparse matrix storing formats [closed]
I have recently done a rather extensive numerical study of the effect of sparse matrix storing formats on the runtime of matrix-vector products. In particular, I considered the following formats: CSR, ...
6
votes
2
answers
148
views
Eigenvalue of diagonally dominant matrices
I want to ask a question about eigenvalue of diagonally dominant matrices.
The question is :
Assume $A=(a_{ij})_{n\times n}\in M_n(\mathbb{R})$ and $\lambda_1,\lambda_2,
\cdots,\lambda_n$ are the ...
- 937
0
votes
0
answers
17
views
Precomputing inverse with unknown diagonal
Given an invertible matrix $A$. I like to compute the matrix inverse, with diagonal matrix $D$, i.e.,
$$
f(D) = (D - A)^{-1}.
$$
Is there a way to precompute something to accelerate the evaluation of ...
- 577
0
votes
3
answers
39
views
Adding the constant column increases the rank of symmetric non-full ranked matrix
Assume we have some symmetric Laplacian matrix $\mathbf{A} \in \mathbb{R}^{n\times n}$ with $rank(A) = n-1$.
Then, let us consider matrix $\mathbf{B} \in \mathbb{R}^{n+1\times n}$, which is matrix $\...
- 85
0
votes
1
answer
47
views
Numerical Inversion of Elliptic Operator
I am trying to solve the following elliptic differential equation.
$$
\frac{\partial^2\psi}{\partial R^2} + \frac{\partial^2\psi}{\partial Z^2} - \frac{1}{R}\frac{\partial\psi}{\partial R} = S(R,Z)
$$
...
0
votes
1
answer
33
views
SVD-based low-rank approximation doesn't work
Let $M$ be a matrix. Consider the singular value decomposition
$$ M = U \Sigma V^*. $$
I've often been told that you can get the best low-rank approximation of $M$ using the SVD. Namely, you split up ...
- 259
1
vote
0
answers
48
views
Approximating a First Order PDE using Finite Difference Method
I'm attempting to approximate the solution $u(x,t)$ to the PDE $x\cdot u_x=t\cdot u_t$ with the initial condition $u(x,t_0)=f(x)$, boundary conditions $u(x_0,t)=g_1(t)$ and $u(x_n,t)=g_2(t)$, and ...
- 11
2
votes
1
answer
368
views
Iterative algorithm for computing $\Sigma^{1/2} x$
Say I have a PSD matrix $\Sigma$ and a vector $x$, is there an iterative algorithm (faster than computing $\Sigma^{1/2}$ using Cholesky decomposition) for computing $\Sigma^{1/2} x$?
(In this ...
- 4,412
0
votes
1
answer
76
views
Why is in Matlab exp(pi * sqrt(163)/3) - 640320 = -2.3283e-10
Why is in Matlab
$$
e^{\pi\cdot\frac{\sqrt{163}}{3}} - 640320 = -2.3283 * 10^{-10}
$$
exp(pi * sqrt(163)/3) - 640320
ans =-2.3283e-10
I know that it does have ...
- 11