Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [numerical-linear-algebra]

Questions on the various algorithms used in linear algebra computations (matrix computations).

Filter by
Sorted by
Tagged with
1
vote
0answers
27 views

Solving Crank-Nicolson type nonlinear vector equation

Given is the following (Crank-Nicolson discretized) equation, \begin{equation} \mathbf{v}_{n+1}+\alpha\Big[\mathbf{A}_{n+1}\,\mathbf{v}_{n+1}-\mathbf{v}_{n+1}\left(\mathbf{v}_{n+1}^*\,\mathbf{A}_{n+1}\...
2
votes
1answer
43 views

Solving a linear system in matrix notation

I'm trying to implement the paper "Conformation Constraints for Efficient Viscoelastic Fluid Simulation": https://www.gmrv.es/Publications/2017/BGAO17/SA2017_BGAO.pdf In implementing eqn. 6, they ...
0
votes
1answer
36 views

Reducing a Least sqare with equality and inequality constraints problem.

First, i know that there are a lot of topic about thoose kind of questions, but i thought about a reducing approach that i did not found in the litterature and i wander if the following steps are OK ...
1
vote
1answer
58 views

importance of Krylov subspace

Can someone please explain to me why we are using Krylov subspaces for the CG-Method, GMRES-Method and Arnoldi. Unfortunately I do not see where the advantages are und why Krylov subspaces are so ...
2
votes
0answers
33 views

Influence of Condition Number on Arnoldi Method

I am currently working with finite elements. Goal is to find the first n eigenvalues and eigenvectors of a generalized eigenvalue problem. After some research I found the Arpack package (I am using ...
1
vote
1answer
32 views

Can the power method give the spectral radius of a nonnegative asymmetric matrix?

I have a large sparse nonnegative asymmetric matrix $A$. Since the matrix $A$ is nonnegative, its spectral radius $\rho(A)$ is an eigenvalue of it. But $A$ may have other eigenvalues being the same ...
0
votes
2answers
75 views

Can we anything say about $y^T y$ if we know $X^T X$ and $X^T y$

Let $y \in \mathbb{R}^n$ and $X \in \mathbb{R}^{n \times p}$, where $n > p.$ We don't know the matrix X, but assume we do know $X^T X$, and make any necessary assumptions about its rank. Assume ...
0
votes
1answer
33 views

What is the complexity order of Kalman rank condition?

Does computing the Kalman rank condition of an integer matrix have complexity polynomial in the size of the input? if yes what is the order of complexity? For a discrete-time linear state-space ...
0
votes
1answer
23 views

Matrix calculations in second order polynomial approximation

I am looking at second order polynomial approximation, specifically at this link. However, I am stuck in the one dimensional case: I do not think I can calculate the following: $$ X^{T}*X^{-1}*X^{T}...
0
votes
1answer
41 views

Solving a vector-matrix-vector equation as part of an iterative process.

For a problem I am working on, it would be really nice to solve the equation \begin{equation} \mathbf{c}_{i+1}^\dagger \mathbf{S}_{i+1} \mathbf{c}_{i+1} = \mathrm{const.} = \mathbf{c}_i^\dagger \...
0
votes
0answers
40 views

A rank puzzle, or finding the implicit form of a Bézier curve without resultants

I've recently completely reworked the code in my Kinross library that finds the intersection of Bézier curves. I've come a long way from first developing my own method and asking for better ones, then ...
0
votes
0answers
40 views

Complexity of matrix-vector multiplication for Kronecker products

Considering the following matrix-vector multiplication: \begin{align} (A\otimes B)x \end{align} where $A$ is $n\times n$ matrix and $B$ is $m \times m$ matrix. In naive way, it can be computed with ...
1
vote
1answer
39 views

How to prove spectral radius is a matrix single eigenvalue?

I have some difficulty in proving the following proposition about non-negative matrix which means that every element of it is non-negative. Suppose $A$ is a non-negative matrix. If there exist a $...
0
votes
0answers
18 views

Set forms an orthogonal basis for Krylov space in 2-norm

Consider the conjugate gradient method for solving $\mathbf{A}x=b$, where $\mathbf{A}$ is symmetric positive definite. With an initial iterate $x_0$, set $p_0 = r_0 = b - \mathbf{A}x_0$. For $ k = 0, ...
0
votes
0answers
17 views

Invert matrix from a 4D array : equivalence or difference between the indexes taken

I have a 4D array of dimension $100\text{x}100\text{x}3\text{x}3$. I am working with Python Numpy. This 4D array is used since I want to manipulate 2D array of ...
0
votes
1answer
36 views

Specific maps from singular matrices to nonsingular matrices

Suppose $A$ is a real, square matrix which is singular, and call the entries $a_{i j}$. Let $f$ be a real valued function and consider the matrix $A^f$ whose entries are $f(a_{i j})$. Are there any ...
0
votes
1answer
74 views

How to find a non-singular matrix $T$ such that $ST\Lambda T^{-1}$ is Hermitian

Let $S$ be Hermitian and $\Lambda$ be an arbitrary complex matrix of the same size as $S$. Is it possible to find an invertible matrix $T$ such that $ST\Lambda T^{-1}$ Hermitian? Does $T$ have any ...
2
votes
2answers
134 views

Condition number and $LU$ decomposition

Consider $A: n \times n$ non-singular and the factors $L$ and $U$ of $A$ obtained with partial pivoting strategy, such as: $PA = LU$. Proof that $$\kappa_{\infty}(A) \geq \dfrac{||A||_{\infty}}{\...
1
vote
1answer
68 views

The reduction of SVD to an eigenvalue problem

Let $A$ be a square $n \times n$ matrix with SVD $A = U \Sigma V^T$. In Numerical Linear Algebra (Trefethen and Bau) it is shown that the symmetric $2n \times 2n$ matrix $$H = \begin{pmatrix} 0 & ...
-1
votes
2answers
45 views

Solving a 4 variable linear system equation with known coefficients

The knowledge is trivial and I'm kinda ashamed to ask, but I am not able to solve the following system using substitution or elimination. $ λP_0 = μP_{1a} + μP_{1b} \\ μP_{1a} + λP_{1a} = λP_0 + μP_2 ...
0
votes
0answers
26 views

Any precise method for solving linear systems with ill-conditioned matrices

Any suggestion on the best method for solving ill-conditioned linear-systems? In my case, the system is proven to have a solution. The method provided here seems to work on PARI/GP to an extent. But ...
0
votes
0answers
30 views

Upper bound of absolute value of a complex function $\left||x| - c\right|$

I have the following relationship: Given $x,y \in \mathbb{C}$ and $c \in \mathbb{R}_{+}$, we have $\left||x| - c\right| = \left|x - e^{j\angle x}c\right| < \left||x| - e^{j\angle y}c\right| $, ...
0
votes
2answers
38 views

Numerical Linear Algebra - eigenvalues

I am coming from the programming world, and I am currently trying to solve a finding eigenvalues problem in a code. HOwever I find it as a very difficult problem to solve in higher matrices dimensions....
1
vote
0answers
35 views

What is the relationship between the matrix norm and singular value decomposition?

I have the following question I am trying to answer but I am constantly failing to. Given $P \in R^{n \times n}$ with $P = U \Sigma V^T$ being its decomposition, what is $||P||^p_p$ ? I'm trying to ...
0
votes
1answer
25 views

Using the power method on a matrix that has been deflated twice

So, according to what I've learned these 4 are true: The power method requires a diagonalizable matrix A A requirement for a matrix to be diagonalizable is that all of its eigenvalues are distinct ...
3
votes
0answers
58 views

How can I apply backpropagation with matrix algebra? - Deep learning

Deep learning and backpropagation is taught out very badly and is often looks like a mess, according to me. So I want to start with a simple example about how to use backpropagation: Assume that we ...
0
votes
0answers
64 views

efficient way to solve $Ax = b$ where $A_{ij} = 0$ for every $i > j+1$

Let $A$ be a square non-singular matrix. Moreover, $A_{ij} = 0$ for every $i> j+1$ , meaning that in every column, from the elements that are under the diagonal, only the first element under the ...
0
votes
1answer
49 views

Powermethod (Eigenvalue problems)

I don't really get it, when the method converges.. The formula I have says that if the eigenvalue with the greatest absolute value has the algebraic multiplicity of 1, and is strictly greater than ...
1
vote
0answers
31 views

Preconditioning for Nonsymmetric Singular Matrices?

I am in a real pickle. I need to solve a linear system $Ax=b$, where A is non-symmetric, singular, and square and of very high dimension. (328x328) I have tried using multistep splitting iterations ...
0
votes
0answers
18 views

Symmetric Linear Map obeying certain relations.

Suppose I have vectors $\mathbf{x}_n$ and $\mathbf{y}_n$ for $n \in \{1, \ldots, N\}$ who are all elements of $\mathbb{R}^P$ with $P > N$. I would like to find a symmetric matrix $\mathbf{A}$ such ...
1
vote
0answers
24 views

Implicit 2D finite difference linear system

I am familiar with the 1D implicit method which solves the heat equation with homogeneous Dirichlet conditions, $$u_i^{j-1} = \big(1+2\lambda)u_i^j - \lambda \big( u_{i+1}^j + u_{i-1}^j \big) $$ ...
0
votes
0answers
50 views

Solution for two equivalent optimization problem based on KKT conditions

Suppose I have the following two optimization problem: \begin{equation} \begin{aligned} & \mathcal{P}_{1}: && \underset{{\bf a}, {\bf b}}{\text{min}} \; \; {\bf 1}_K^T {\bf a} \\ & \...
0
votes
1answer
66 views

Spherical coordinates w.r.t. nonstandard basis vectors

Linear algebra / Matlab question: in $\mathbb{R}^{3}$, let's say that I have an orthonormal basis, $\{v_{1},v_{2},v_{3}\}$, that is not the standard Euclidean basis vectors, ($e_{1}=(1,0,0)$, $e_{2}=(...
0
votes
1answer
55 views

Creating Null space of a symmetric tridiagonal matrix : Finding vector $v$ such that $Av = \vec{0}$

Let $A$ be an arbitrary matrix. By definition, null space of $A$ is the space made by set of vectors $x$ such that $Ax = \vec{0}$. Let $$ A = \begin{bmatrix} a_1&b_1&0&0& \cdots &...
3
votes
0answers
67 views

Adding identity to invert matrix

I'm looking into algorithm implementation which is essentially linear regression: $$\|Ax - b\| \rightarrow \min$$ Matrix A and vector b are estimated using data, then we do $A^{-1}b$ to find x. But ...
1
vote
0answers
34 views

Eigenvalues of sum of two matrices

I have a family of matrices depending on a parameter $\mu$ of the form: $$A(\mu)=A_0+D(\mu),$$ where $D(\mu)$ is a diagonal matrix and $A_0$ does not depend on $\mu.$ The diagonal of $D(\mu)$ is a ...
0
votes
1answer
122 views

Inverse of a large sparse matrix in Matlab

Background: Let $\Omega$ be the state space of an absorbing Markov chain with $\Omega_a$ being the set of absorbing states, and its complement $\Omega_a^c$, being the set of transient states. The ...
2
votes
1answer
66 views

Computing/certifying bounds for eigenvalue computations for big sparse 0-1 matrices

I am finishing my PhD, and at some point I give some bounds on let's say a constant $\lambda$. This constant is the maximum eigenvalue of a matrix $M$ with only zeroes and ones (so the Perron-...
1
vote
1answer
46 views

Positive semidefinite inequality

Let $\mathbf{A}\in\mathbb{C}^{m\times m}$, and $\mathbf{B}\in\mathbb{H}^{m\times m}$ be an $m$-dimension Hermitian matrix, solve $\theta$ that satisfies the condition \begin{equation*} e^{\jmath\theta}...
3
votes
1answer
83 views

Complexity of computing the leading singular vector for an $n\times n$ real matrix.

We know that doing a full svd for an $n\times n$ real matrix is $\mathcal{O}(n^3)$. What about just computing the leading singular vector, say using the Lanczos algorithm? It's certainly better than $\...
0
votes
0answers
37 views

Accurate method for computing the inverse of a matrix

I am looking for an algorithm to compute the inverse of a matrix. I have tried some algorithms that by increasing the dimension of the matrix give a bad result. Mathematica's code works properly even ...
0
votes
0answers
26 views

Why is the minimun error bounded in Bauer-Fike's Theorem of eigenvalue computation conditioning instead of the maximum one?

This is Bauer-Fike's Theorem Let the matrix $ A$ be diagonalizable and let $ S $ invertible, such that $S^{-1}AS=D=diag(\lambda_1,\lambda_2,...\lambda_n)$ Let $\widetilde{A}$ be a perturbation of ...
0
votes
1answer
47 views

Numerical stability: cannot unitarily diagonalize normal matrices

I am trying to setup small numerical experiments to see if a unitary matrix can be unitarily diagonalized thanks to the spectral theorem: https://en.wikipedia.org/wiki/Spectral_theorem (see normal ...
0
votes
2answers
28 views

Critical Points of Vector Function

Given a matrix $A$ that is $n \times d$ and a $n$-dimensional vector $w$, define the vector function $f$ as: $f(v) = \frac{w^TAv}{||Av||^2}$ where $v$ is a $d$-dimensional vector. How can I find all ...
0
votes
0answers
17 views

Column pivoting criteria: column with maximum value or column with maximum norm

I understand column pivoting is a procedure for attaining numerical stability(correct me if I am wrong). I am studying QR factorization now. I have encountered couple of ways of pivoting columns, ...
0
votes
0answers
19 views

Optimizing a system of equations to minimize purchasing cost

I am new to this (posting on stack exchange and higher level math in general) so please correct me where I am in error. I am trying to minimize the cost to my company for purchasing a certain product. ...
1
vote
1answer
44 views

QR Algorithm and tridiagonal matrix

Consider $A: n \times n$ a symmetric matrix. a) Explain the main steps to perform on Orthogonal transformations so as to to obtain a matrix $T$, tridiagonal, orthogonally similar to $A$. b) ...
-1
votes
2answers
44 views

Exercise about eigenvalue

Consider $A: n \times n$, Hermitian matrix, and the ordering of eigenvalues: $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$. Prove that: $\lambda_1 = \max (x^{H}Ax)$ and $\lambda_n = \min (...
0
votes
0answers
32 views

Solving a system of non linear equations (which can be solved in some special cases)

I am trying to solve the following system of $n^2$ equations for $X$ $c_i^\top (A_{i,i} B + X)^{-1}(A_{j,j} B + X)^{-1} c_j = I_{i,j}, \forall i,j\in\{1,\dots,n\}$ where $c_i$ is an $n$-dimensional ...
0
votes
1answer
97 views

How to solve $Ax=b$ wihout inverting $A$?

I'm going to solve this equation: $$Ax=b$$ Onto an embedded system with using C-programing language. It need to be fast as possible. Assume that $A$ is not square. One way to solve this is to use: $...