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

learn more… | top users | synonyms

1
vote
0answers
45 views

Setting up Kernel to Numerically Solve Fredholm Equation of Second Kind

I am looking to confirm if what I am doing is the proper procedure. I writing a program to discretely solve a Homogeneous Fredholm Equation of Second Kind that is set up as follows: $ \int ...
1
vote
0answers
19 views

Numerical methods for computing exponential, if I have computed an exponential of a perturbated matrix

I need to compute the product $e^{H_1}\,e^{H_2}\,\ldots\,e^{H_n}$ for antihermitian matrices $H_j$ that do not commute and $H_i-H_{i+1}$ is small. Is there a numerically convenient way to compute ...
0
votes
0answers
30 views

Nearest points / residuals on a total least squares parabola

Consider fitting a parabola $y = a + bx + cx^2$ to 2d data $X_i, Y_i$ with noise in both X and Y, using the the singular value decomposition as in Total_least_squares (TLS): $\qquad X = [ 1\ \ Xdata\ ...
1
vote
0answers
18 views

Transformation between Ideal and Warped Surface

I work on manufacturing metal panels with holes drilled in them. Suppose I have an ideal 3D surface from CAD. I want to compare it to the actual part using reference points to compare between the two. ...
0
votes
0answers
21 views

How can I apply a median filter directly to a time-varying rotation matrix?

I need MatLab script which would take a series of rotation matrices (referring to an actual physical object's orientation) and apply median filter to it to eliminate speckle noise from it. The way ...
2
votes
0answers
67 views

Numerically approximate the maximum of an element of a vector after a series of matrix multiplications.

Where S is a sigmoidal function, A_i is a matrix, and x is an input vector, and ...
0
votes
0answers
42 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
0
votes
0answers
57 views

Complexity of the power method

I'd like to find out what the complexity of the power method is depending on the size of the matrix $A \in \mathbb{R}^{n\times n}$ given that the algorithm runs until a certain stop criterion. I.e. ...
0
votes
0answers
29 views

resources about sparse global constrainted optimization

Please recommend a good resources (books/articles/software) about sparse global constrained optimization?
0
votes
1answer
71 views

Solving 2x2 diagonally dominant matrix systems (non-symmetric)

I have a linear system of the form $Ax=b$ where $A\in \mathbb{R}^{2\times2}, b\in \mathbb{R}^{2\times1}$. A is diagonally dominant and non-symmetric. This is a "kernel" that I am using to solve a ...
1
vote
0answers
39 views

Numerically stable way to compute $\text{Trace}[\mathbf A\mathbf A_1^{-1}\mathbf B\mathbf B_1^{-1}]$

I have two dense (column-major) PSD matrices $\mathbf A$ and $\mathbf B$, $\mathbf A,\mathbf B\in\mathbb R^{n \times n}$ ($n$ is usually $\sim 1000$) and also $\mathbf A_1=\mathbf A+\eta\mathbf I_n$ ...
0
votes
1answer
136 views

Application of Conjugate Gradient Method to non-symmetric matrices

I am currently working on a problem in which I am using the Conjugate Gradient method to solve for the steady state solution of a continuous time Markov chain. I am applying the algorithm found in ...
0
votes
1answer
32 views

Finding SVD of a Matrix

If $a_{1},a_{2} \in \mathcal{R}^{2},$ $\ \|a_{1}\|_{2} = \|a_{2}\|_{2} = K$, and the angle $\theta$ between $a_{1}$ and $a_{2}$ is between $0$ and $\pi/2$, we want to compute the SVD of the matrix $A ...
1
vote
0answers
37 views

How to find the rank of a toeplitz matrix?

Is there any trick to compute or estimate the rank of a toeplitz matrix ? Or is this still unknown for a general toeplitz matrix ?
4
votes
2answers
93 views

Rewriting the matrix equation $AX = YB$ as $Y = CX$?

Is it possible in general, if $A,B,C,X,Y$ are square and of the same dimensions? If so, does it generalize to non-square matrices (using a pseudoinverse)? I'm doing some curve fitting in which I have ...
0
votes
2answers
64 views

Spectral radius and iterative method convergence

I'm trying to show that if the spectral radius of $R$, $\rho(R)\geq 1$, then there exist iterations of the form, given $\mathbf{x}_0$, $\mathbf{x}_{n+1}=R\mathbf{x}_n+\mathbf{c}$ Which do not ...
0
votes
1answer
68 views

Proving boundedness of a function (part 1).

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
0
votes
0answers
57 views

estimate an upper bound for the error of an interpolation polynom

The task is to estimate the error of an interpolation polynom $p(x)$ to an function $f(x)$. The sampling points are $x_0 = -1,\ x_1= 0,\ x_2=1,\ x_3=3$ So i already calculated the polynom which does ...
2
votes
3answers
207 views

How to reverse matrix vector multiplication?

I'm using the simple matrix x vector multiplication below to calculate result. And now I wonder how can I calculate ...
1
vote
0answers
38 views

Iterative methods for solving a linear equation system

There are several methods known for solving a linear equation system Ax = b (like Jacobi or Gauss-Seidel) by iterating $x_{n+1}=Mx_n+c$ with a matrix M, for which some norm is smaller than 1. But ...
2
votes
1answer
37 views

A generalization of GMRES

In oder to solve $Ax=b$, GMRES method finds $x_n$ in the $k$-th Krylov subspace i.e.: $$K_n=span\{b,Ab,...,A^{n-1}\}$$ and we have the condition: minimize $\|r_n\|_2$, which $r_n=b-Ax_n$ Now we ...
1
vote
0answers
36 views

Solving tridiagonal matrices where the top left element is zero

If I have a matrix like this: $$ \left[\begin{array}{rrrrrrrrr|r} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & ...
0
votes
0answers
29 views

Finite difference method for elliptic pde stability condition

I am trying to implement a finite difference scheme for the elliptic pde $\nabla(a(x_1,x_2)\nabla\phi(x_1,x_2))=0$ where $(x_1,x_2) \in (0,l_1)\times(0,l_2)$ with $l_1 \neq l_2$ necessarily. I know ...
2
votes
1answer
50 views

Positive definite martix

I understand the majority of this solution, it's just I don't understand why I have to use both $\epsilon_1 $ and $\epsilon_2 $ rather than just $\epsilon$. I understand that i'm working with ...
0
votes
2answers
50 views

Least Squares Solution Confusion

Say if I have an overdetermined system $A\vec x=\vec b$, I can use the normal equations $\implies$ $A^TA\vec x=A^T\vec b$. If I solve for $\vec x$ I will get a "solution" with an error. It says in ...
2
votes
1answer
72 views

QR transformation with Householder transformation

It's a task i do to understand minimizing the error including the QR transformation with the help of Householder transformation. I think i really do something wrong but i dont get it running i hope ...
1
vote
0answers
51 views

Numerical rounding errors in intersection code

I hope this question is in the right place, as it is as much about programming as it is about math. I'm trying to find the intersection between a circle and a line. My implementation of the algorithm ...
0
votes
0answers
38 views

Efficient Factorization for Family of Matrix Equations

I am looking for an efficient solution to the following problem $$ A+\lambda I = b \tag{1} $$ where $A\in\mathbf{S}^{n}$ is a symmetric matrix with nonzero eigenvalues, $b\in\mathbf{R}^n$ is fixed, ...
3
votes
1answer
91 views

I want to study Numerical linear algebra [closed]

Would you like to recommend a book to me? the proof is explicit and easy to understand is preferred.
1
vote
0answers
51 views

Gaussian elimination vs. Jacobi iteration

How can I determine which of the matrix solver is faster for a given set of equations: Gaussian elimination or Jacobi iteration? In case, I have a banded matrix, is it advisable to use LU ...
1
vote
0answers
45 views

When is the LU decomposition unique?

I want to find out when a matrix decomposition $A = LU $ (L lower and U upper matrix) is unique? Clearly, if $A$ is not invertible, there is no chance that this decomposition is unique. Hence, ...
0
votes
1answer
49 views

Simplying linear equation to get quartic in q using Maple and then using Descarte’s rule of sign

Using the maple I am trying to get quardic in q from this big linear equation. Then use Descarte’s rule of signs to determine the number of positive roots. \begin{equation} ...
0
votes
1answer
45 views

Solve for a matrix in a linear equation

This is probably a really basic question, but we are stuck and the usual keyword lead to the normal "Solving linear equations with matrices"/Gaussian-elimination pages ... I have an equation $A X B + ...
2
votes
2answers
76 views

Determinant of an ill conditioned matrix

I have the following ill conditioned matrix. I want to find its determinant. How is it possible to calculate it without much error \begin{equation} \left[\begin{array}{cccccc} ...
0
votes
0answers
44 views

System of linrar equations and condition number

The relative error of the solution of a system of linear equation $Ax=b$, for any natural norm $\|\cdot\|$ is bounded by $$ \frac{1}{\| A\| \|A^{-1} \|} \frac{\|r\|}{\|b\|} \le \frac{\|e\|}{\|x\|} \le ...
0
votes
1answer
112 views

condition number of orthogonal matrix

Let $A\in M_n(\mathbb R)$ be an orthogonal matrix. Then: $cond (A) =1$. I tryed to use facts about the eigenvalues but is did not help. In 2-norm it is easy to prove it since $||A||_2 = \sqrt{\rho ...
0
votes
1answer
65 views

Spectral norm of a Hadamard product

Let $F$ be the $n\times n$ DFT matrix, i.e., $F_{i,j} = \exp\left(-\tfrac{2\pi(i-1)(j-1)}{n}\imath\right)$, for $1\le i,j\le n$ and $\imath =\sqrt{-1}$. Futhermore, let $\Vert \cdot\Vert$ and $\odot$ ...
0
votes
2answers
24 views

Finding a rotation matrix

I am looking for a rotation matrix such that $$ \operatorname{rot} \cdot \begin{pmatrix} -1 & 0 & 0 \\ 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{pmatrix} = ...
1
vote
1answer
129 views

Efficient Algorithm for Iteratively Reweighted Least Squares Problem

I'm interested in solving a weighted least squares problem of the form $X^T W X \beta = X^T W Y$ where $W$ is a diagonal, positive definite matrix, $X \in R^{m \times n}$, $Y \in R^{m \times 1}$ and ...
3
votes
2answers
85 views

Power iteration

If $A$ is a matrix you can calculate its largest eigenvalue $\lambda_1$. What are the exact conditions under which the power iteration converges? Power iteration Especially, I often see that we ...
1
vote
1answer
50 views

Lipschitz continuity for generalized inverse matrix

Suppose $A$ and $B$ are full-rank and well-conditioned. Is Lipschitz continuity held for generalized inverse? $$\|A^+ - B^+\| \le \omega \|A-B\|,$$ for some $\omega > 0$, where the norm could ...
0
votes
1answer
17 views

LD$t(L)$ factorization and eigenvalues

A positive definite matrix $A$ can be factored in to $LDt(L)$form. Is the statement the eigenvalues of $A$ are the diagonals of $D$ true? If so , how to prove it?
3
votes
0answers
56 views

Does anyone know any reference for this matrix?

For $n \geq 4$, $A$ is $(n-1) \times (n-1)$ tridiagonal block matrix $$A = n^2 \begin{bmatrix}B & -I & 0 & \cdots & \\-I & B & -I & 0 & \\ 0 & -I & B & -I ...
2
votes
2answers
48 views

Solving $a_1x_1 + \cdots +a_nx_n = b$

I'm glad to ask my first question on the maths site! So here we go. I'm trying to set up prices right now and here is my problem : I know that my customer has a certain amount of money available. ...
2
votes
1answer
50 views

Can an iterative method converge for some initial approximation?

Studying iterative methods for solving(or approximating) linear equation systems, I came accross the following theorem$^1$: Let the following be an iterative method: $$x^{(0)},\qquad known\\ ...
2
votes
1answer
151 views

Inverse of constant matrix plus diagonal matrix

Is there an efficient way to calculate the inverse of an NxN diagonal matrix plus a constant term? I am looking at N of around 40000. $\left[\begin{array}{cccc} a & b & \cdots & b\\ b ...
2
votes
1answer
69 views

Linear equation: $(A^\top A+B^\top B + D)x=c$ where $A,B$ are structured sparse and $D$ is diagonal.

Updated: the goal is to solve $(A^\top A+B^\top B + D)x=c$. Maybe it is not necessary to compute $(A^\top A+B^\top B + D)^{-1}$. Denote $e=(1,1,\ldots,1)^\top\in\mathbb{R}^n$ and ...
1
vote
1answer
43 views

Consistency of the system $AX=b$

In the concept of consistency (compatibility) of a matrix, when $b \in \mathbb R (A)$ we know for sure that the system is consistent or there may exists no solution for it? But when $b \notin \mathbb ...
0
votes
2answers
30 views

Formatting Linear equation

How do I craft a linear equation so that it is in the form of $ax + bx + c = 0$ where $a^2 + b^2 = 1$ if I have two points? I know how to get it into the form $ax + bx + c = 0$ but I can't figure out ...
1
vote
0answers
38 views

Check feasibility of a system of integer linear equations

I'm currently working on a very large integer linear programme which cannot be solved within any reasonable time. The initial set of linear equations S={Ax<=b) is feasible. I want to add more ...