Stack Exchange Network

Stack Exchange network consists of 175 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).

1
vote
0answers
40 views

Book for manifolds that are used in scientific computation

I've been reading up on papers in scientific computation that utilize terms such as "Stiefel manifold" and "Grassmannian" that seem to be invoked in numerical linear algebra. I don't have any ...
0
votes
0answers
29 views

Confusion about Numerical Stability

Numerical Analysis is giving me some trouble. In specific, I'm highly confused by our definition of numerical stability. I'm hoping some of you can help me clear my confusion. Definition. An ...
0
votes
1answer
37 views

Is there any relation between SVDs of two matrices with same range?

Let $A$ and $B$ be two symmetric and positive semidefinite matrices with the same size. Further, assume that $A$ and $B$ share the same column space (i.e., $\mathcal R (A) = \mathcal R (B)$ ). Is ...
0
votes
0answers
43 views

Motive of Conjugate Gradient method.

It is known that the solution to the linear system $Ax=b$ where $A$ is symmetric and positive definite is the minimizer of the quadratic function $f(x)= \frac{1}{2} x^T A x - x^T b$ We can solve it ...
1
vote
0answers
14 views

Variety of submodules of a finitely presented module

Assume that $A$ is a graded $k$-algebra with $A_d=k$ in every degree $d$. Let $M$ be an $A$-module with finite free presentation $F_1\to F_0\to M\to 0$. I want to undertand the collection of finitely ...
2
votes
1answer
118 views

Householder transformations to upper triangular form

Let $A=\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$. How to transform this matrix with Householder transformations to an upper ...
-1
votes
1answer
17 views

Efficiency in matrix multiplication with diagonalizable matrix. [closed]

Are there efficient algorithms to compute Ax in the case of A being diagonalizable instead of not being?
1
vote
1answer
38 views

Convergence of CG method, number of eigenvalues

I am trying to fix this proof of a lemma that I did't correctly write: If $A\in \mathbb{R}^{n\times n}$ symmetric positive definite with $m$ different Eigenvalues $\lambda_j$, then the Conjugate ...
0
votes
1answer
50 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
142 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
52 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
86 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
64 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
29 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
17 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
41 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
114 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
39 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
61 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
66 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
102 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
29 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
21 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
276 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
36 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
35 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
80 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
27 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
37 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
29 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
45 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
73 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
22 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
1answer
32 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
42 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
96 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
42 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
68 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
26 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
75 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
50 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\\ ...
1
vote
0answers
51 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
15 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 ...
1
vote
1answer
187 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
79 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
238 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
76 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
144 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
54 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
101 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({...