Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [numerical-linear-algebra]

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

0
votes
1answer
38 views

Can we simplify $ A^{-1}Bx = x$ where $A$ is a block matrix with each block being diagonal and half the blocks of $B$ are zero?

I have the following eigenvalue problem involving block matrices $A$ and $B$: $$ A^{-1}Bx = x. \quad \quad \quad \quad (*) $$ $A$ and $B$ have special structures. I would like to reduce/simplify this ...
0
votes
1answer
28 views

Is it possible to find complex eigenvalues with QR decomposition?

I wonder if it's possible to find the complex eigenvalues with QR decomposition. I can find the real eigenvalues with QR just by doing this. ...
0
votes
0answers
17 views

Orthogonalize two sets of vectors against one another

Given two subspaces $U,V\subset \mathbb{R}^n$ and orthonomal bases $U = \{u_1,\ldots,u_p\}$ and $V = \{v_1,\ldots, v_q\}$ (wlog $p\geq q$) is there a fast way to compute an orthonormal basis for $U+V$?...
0
votes
2answers
73 views

Bring ODE into a suitable form to solve it with Runge-Kutta steps

Can anyone please help me understand, how I should bring this ODE y'' + y = sin(t) with initial conditions y(0) = 100, y'(0) = 5 into a Runge-Kutta-Form? I tried to solve this equation, the ...
-1
votes
1answer
43 views

What is the best algorithm to find the inverse of matrix $A$

I'm going to build a C-library so I can do linear algebra at embedded systems. It's most for machine learning. https://github.com/DanielMartensson/EmbeddedAlgebra/ Anyway, I need to compute inverse ...
0
votes
1answer
21 views

Calculating the real triagonal form from a complex triagonal matrix

I am writing a custom 3x3 Matrix Exponentiator in C for specific complex Hermitian matrices of the form $$ \left(\begin{matrix} q+z & x-iy & 0 \\ x+iy & 0 & x-iy \\ 0 &...
0
votes
0answers
12 views

Condition number of a square matrix with entry $A_{ij}$ being $j^{2i-1}$ and numerical stability for $Ax=b$

$i,j \geq 1$ (that is row $i$ and column $j$ counting start from $1$), and let entry $A_{ij}$ of the $n \times n$ square matrix $A$ be defined as $A_{ij} = j^{2i-1}$. Without fixing $n$, would there ...
2
votes
0answers
29 views

Inverting the sum of a circulant and a diagonal matrix

Is there an efficient way of (numerically) solving a linear system, where the matrix is a sum of circulant and diagonal matrices? I need to solve a linear system of the form (V+D)x=y where V is a ...
1
vote
2answers
35 views

Actual computational complexity of solving a linear system accounting for numerical accuracy (digit)

Solving a system of linear equations is solving for $n \times 1$ vector $x$ out of $Ax = b$, where $A$ is $n \times n$ matrix. Suppose that $A$'s entries have $k$ digits at maximum, in binary or ...
2
votes
1answer
34 views

Choose diagonal matrix $D$ to make $DB$ as orthonormal as possible

Let $B\in \mathbb{R}^{m\times n}$, $m>n$. How can I choose $d_1,\dots,d_m$ such that $DB$, with $D_{ij} = d_i \delta_{ij}$, $1\leq i,j\leq m$, is not far from orthonormal, i.e., $\|B^{T}D^{T}DB-\...
1
vote
1answer
30 views

Equivalency of simultaneously block diagonalizing two matrices and finding invariant subspaces

@Victorliu specified in a comment for this question: "Block diagonalizing two matrices simultaneously is equivalent to finding invariant subspaces common to both matrices". There are two questions ...
0
votes
0answers
27 views

Calculating the distance function on a manifold, given the Riemannian metric in matrix form

I come from a CS background (and this is for a CS project) and as such my skills and knowledge of geometry are pretty poor. I'm looking at a bunch of points on a Riemannian manifold (let's say, for ...
4
votes
0answers
94 views

Least square problem constrained to projection matrices

Some times in engineering, it is important to find an optimum subspace in which projecting on it satisfies some properties. Let known matrices $A$ and $B$ belong to $\mathbb{R}^{p\times n}$ and $\|\...
0
votes
1answer
17 views

SVD Inequality for Block Matrices

Suppose that $A \in \mathbb{C}^{m \times n}$, $m \geq n$, has the block form $$A = \begin{bmatrix} A_1 \\ A_2 \end{bmatrix} $$ where $A_1 \in \mathbb{C}^{n \times n}$ and $A_2 \in \mathbb{C}^{(m-n) \...
0
votes
0answers
19 views

Understanding the relation between Sweep operator and Graph rotation.

In this blog post, the sweep operator from numerical linear algebra was explained. It was all clear until, the post says that Any ${n \times n}$ matrix ${A}$ creates a graph ${\hbox{Graph}[A] := \{ (...
3
votes
0answers
220 views

Woodbury Matrix Inversion

I am trying to invert a matrix using Woodbury identity. The inversion using Cholesky decomposition has the following pseudo-code: For $t=1,2,...$ $(1)\;\; \text{Read}\;x_t\in\mathbb{R}^n$ ...
0
votes
0answers
30 views

Tips for optimisation problem

I have an optimization (minimize) problem which can be written down as: $f(\vec{x})=\sum_1^m{(max(\vec{a_1}*x_1,\vec{a_2}*x_2,\vec{a_3}*x_3,...,\vec{a_n}*x_n)-\vec{a_0})^2}$ Where $m$ is the size of ...
0
votes
0answers
21 views

The integration of Legendre functions

We know the integration of Legendre wavelet function is $\int_{0}^{T}\Psi(s)ds=P.\Psi(t)$. We can find the matrix $P$ as follows. My question: I want to learn how to find Matrix $P$. I can' t ...
0
votes
0answers
19 views

FInding smallest eigenvalues using Lanczos algorithm

I have some trouble understanding how Lanczos algorithm works for finding $K$ smallest eigenvalues of some large symmetric matrix $A$. For example if I want to calculate 50 smallest eigenvalues of $...
0
votes
1answer
18 views

Krylov Space dimension for specific matrix

This was an exam question and I couldn't solve it so I'd like to know what the solution is. Let $b,c\in \mathbb{R}^n$ be linearly independent and define $$A(b,c)=I+bb^T+cc^T.$$ Show that ...
2
votes
1answer
34 views

Approximation of a matrix in the power method

Here's the text of the problem ( here $\lVert\cdot\rVert$ denotes any matrix induced norm): Let be $A\in \mathbb{R}^{n\times n}$ a diagonalisable matrix $n\times n$, with $\lambda_{1}, \lambda_{2},\...
0
votes
1answer
24 views

Multiplications that preserve singular values

What is the characterization of matrices $B$(not necessarily squared) such that $BA$ has the same largest singular value as $A$? How about when $BA$ preserves the same $k$ largest singular values of $...
0
votes
1answer
14 views

How do I determine the weights and abscissas in the 1 and 2-point Gauss quadrature given a weight function?

Determine the weights and abscissas in the 1 and 2-point Gauss quadrature formulae for $\int_{0}^1 f(x)w(x)dx$ with weight $w(x) = − \ln x$. I'm pretty confused on how to approach this problem with a ...
0
votes
0answers
23 views

tensor power method

Just as we can use the matrix power method to find eigenvalues/eigenvectors of matrices in an iterative way, we can analogously find the eigenvalues/eigenvectors of tensors in a similar way. My ...
0
votes
1answer
15 views

Trouble solving for the Jacobian update formula in Broyden's method

I'm having trouble understanding how to update this formula (it's Broyden's method in multiple dimensions) by solving the following equations: $$A^{(m)}(x^{(m)}-x^{(m-1)}) = f(x^{(m)})-f(x^{(m-1)})$$ ...
0
votes
0answers
17 views

What is the largest condition number a 64-bit computer can take to do matrix inversion to give good result?

In my problem, it looks like $10^{13}$ is a red-line, once it crosses, the performance of matrix inversion goes down. But why? Or do you have better idea for that?
0
votes
1answer
30 views

Numerical Analysis - $n$-sided polygon tangential

i need help with this question..I'm not so sure how to go about the arguments. Any help would be appreciated. Consider a regular $n$-sided polygon tangential to and enclosing the unit circle to ...
0
votes
0answers
30 views

Linear system with Non-square LU factors

Consider the following linear system of equations: $$ \textbf{A}\textbf{x} = \textbf{b} $$ Where $\textbf{x}, \textbf{b} \in \mathbb{R}^{n}$ and $\textbf{A} \in \mathbb{R}^{n \times n}$. We also have ...
0
votes
1answer
26 views

Finding the householder transformation given $P = P(w)$ such that $P(w) x = e_{1}$

The matrix $$A =\begin{bmatrix} 2 & 10 & 2 \\ 10 & 5 & -8 \\ 2 & -8 & 11 \\ \end{bmatrix}$$ has an eigenvalue $\lambda = 9$ with the corresponding eigenvector $...
0
votes
0answers
31 views

Solving linear equations system using inverse matrix and finding back this matrix by using linear equations

I stumbled into this question in the course of some experiment: I had this system of linear equations: m = 1a+2b+3c+4d n = 2a+3b+4c+1d o = 3a+4b+1c+2d p = 4a+1b+2c+3d I have no fixed values for ...
2
votes
1answer
53 views

Distance from eigenspace of matrix

In linear algebra, is there a separate name / concept for the notion of distance between linear vector subspaces? I'm asking this because I'm considering a problem in numerical linear algebra where ...
0
votes
1answer
24 views

The expected value of the second pivot in gauss jordan eliminaton

Say I have a matrix x1 x2 x3 x4 With x1, x2, x3 and x4 randomly and uniformly drawn from the interval [0,1] After I do gauss-jordan elimination, what is the ...
0
votes
1answer
58 views

Boundedness of the spectral radius of matrices $A^h$ as $h\to 0.$

I need to know if the following matrix has a bounded spectral radius $\rho(A)$, as $h\to 0:$ $$A^h=\frac{1}{h^2}\begin{pmatrix} h^2-2h-2&2&0&0\dots &0\\ 1&h^2-2&1&0\dots &...
1
vote
1answer
34 views

How to block diagonalize a real skew-symmetric matrix of 3*3

Suppose $t = [t_1,t_2,t_3]^T\in \mathbb R^3,t \neq 0$. Then define $$t^{\land} = \begin{bmatrix} 0 & -t_3 & t_2 \\ t_3 & 0 & -t_1\\ ...
0
votes
0answers
17 views

How to find a sparse basis of the null space of a large sparse matrix using QR decomposition

Suppose that we have a large sparse matrix $A\in{\mathbb{C}}^{m\times n}$, $m<n$, and $A$ is row full rank. Let $V$ be the solution set to $Ax=0$, and we know that $V$ is a linear space and $\dim(...
0
votes
0answers
13 views

Tychonoff Regularization by calling an Optimization Routine

Question : Set $ X = [−1,1]$ let $u_c(x)=sin(\pi x) $ be a clean signal. Add noise $n(x)$ which is mean zero with variance $σ^2=0.1^2$ and let $u_n=u+n$. Let, $ 0 = x_1,......,x_n = 1$ be an equally ...
0
votes
1answer
50 views

Outer product reformulation of LU decomposition

For my numerical analysis class, I wanted to implement the rather simple, in-place LU decomposition algorithm. I did this the naive way and found my code was very, very slow, because I was doing every ...
1
vote
3answers
64 views

Is $det(A)=0$ a good indicator to say that a matrix is not invertible?

In finite elements, for example, appears huge sparce (CRS) matrices (matrices with a lot of zeros). It is possible that matlab (or some other program) calculates $det(A)=0$ even though the matrix is ...
-1
votes
2answers
49 views

How to inverse a block diagonal matrix?

Given a matrix $$x = \begin{bmatrix} 40 & 0 & 0 & 0\\ 0 & 80 & 100 & 0 \\ 0 & 40 & 120 & 0 \\ 0 & 0 & 0 & 60\end{bmatrix}$$ How to find the inverse of ...
0
votes
0answers
54 views

Why does the Lanczos algorithm fail on repeated/multiple eigenvalues?

I'm trying to code up the Lanczos algorithm for eigenvalue approximation at the moment. I've seen on pages like this that the algorithm can't distinguish the eigenvectors if the dimension of the ...
1
vote
2answers
39 views

Generating a random sparse hermitian matrix in Python

I'd like to find a way to generate random sparse hermitian matrices in Python, but don't really know how to do so efficiently. How would I go about doing this? Obviously, there are slow, ugly ways to ...
0
votes
1answer
52 views

Estimate the number of iterations

Construct $A =Q\Lambda Q^T$. $Q$ is found by applying $QR$ factorization to $B=$randn($n$), and $\Lambda$ is defined to be \begin{align*} \Lambda = \mathrm{diag}(\lambda_1,\lambda_2,\ldots,\...
0
votes
0answers
36 views

Proof that Gauss- Seidel iteration method converges for any initial x if the matrix is self-adjoint and positive-definite

I am trying to create a direct proof that if the matrix A is self-adjoint and positive-definite, then the Gauss-Seidel iteration converges for any initial ${\bf x}_{0}$ I think I need to prove $\rho({...
0
votes
1answer
34 views

Least Squares Solution of Minimal Norm when $A^{*}b = 0$

Suppose, given a matrix $\textbf{A} \in \mathbb{C}^{m \times n}$ and a vector $\textbf{b} \in \mathbb{C}^{n}$, I want to find the minimal norm solution of $$\min_{\textbf{x}}\|\textbf{A}\textbf{x} - \...
1
vote
0answers
24 views

Reduced complexity of matrix inversion of sum of rank 1 matrices: $M^{-1} = \left( I + \sum \limits_{i=1}^{K} \alpha_i A_i \right)^{-1} $?

How to reduce the complexity of matrix inversion of sum of rank 1 matrices, not only arithmetic but also run time? $M^{-1} = \left( I + \sum \limits_{i=1}^{K} \alpha_i A_i \right)^{-1} $ where $A_i ...
0
votes
0answers
26 views

Logical indexing and for loop question Matlab

I have a vector p=[-3 -2 -1 0 1 2 3], and an expression like $\psi_p=a~e^{ikp}+b~e^{-ikp}$ for $-3\leq p< 1$ and $\psi_p=c~e^{ikp}$ for $1\leq p\leq 3$; $a$, $b$...
1
vote
1answer
58 views

Constrained optimization of l2 norm

Consider the problem $min_{x}||x-a||_{2}^{2}$ such that $||x||_{p}\leq 1$ in two dimension. Solve the problem geometrically for the cases $p=1, 2, \infty $ Sketch the solution in the case $||a||_{p}\...
0
votes
0answers
26 views

Proof that if $x$ minimises $\left \| Ax-b \right \|^{2}_2 +\mu\left \| x \right \|^{2}_2$ then it solves regularised normal equations

I'm looking for a proof that if $x$ minimises $\left \| Ax-b \right \|^{2}_2 +\mu\left \| x \right \|^{2}_2$ then it solves $(A^{T}A+\mu I)x=A^{T}b$
0
votes
0answers
16 views

(Worst and average case) Arithmetic and time complexity of a quadratic programming problem by interior point method

My understanding of complexity measures are at basic level. So, please excuse me for asking basic question, if it sounds like. I am trying to understand the arithmetic and time complexity of a ...
1
vote
1answer
49 views

Rayleigh quotient of matrix $A$ is diagonal entry of $Q^*AQ$

Let $A\in \mathbb{C}^{m\times m}$ be a matrix. Show that if $z\in\mathbb{C}$ is a Rayleigh quotient of $A$ then $z$ is a diagonal entry of $Q^*AQ$, with $Q$ a unitary $m\times m$ matrix. My approach: ...