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

learn more… | top users | synonyms

0
votes
0answers
13 views

Are there any sure-fire methods for correctly arranging matricies for Gaussian Elimination?

I am attempting to make a Gaussian Elimination solver for square sparse matrices that are less than 100 by 100 across. I have roughed out a method for filling in the diagonal of the matrix (using row ...
0
votes
4answers
50 views

Shortest Distance between a Point and a Numerical 2D Curve

I have a 2D Curve. I have all the numerical values for the line within a certain range. I do not have an equation for this line. At several points in this 2D space I want to calculate the shortest ...
0
votes
1answer
25 views

Equation that maps two values to three? [on hold]

I'm trying to get an equation for a line in 2-dimensions that maps into an equation for a line in 3-dimensions where $$ f(x,y) => x_1,y_1,z_1 $$ and preferably have a resource that teaches me the ...
0
votes
0answers
13 views

Stuck on condition number derivation of the perturbed equation $(A + \Delta)\tilde{x} = b + \delta_b$

I've almost got what I want. We start with $Ax = b $ and $(A + \Delta)\tilde{x} = b + \delta_b$. What I have then is \begin{align*} \tilde{x} - x &= -A^{-1}\Delta\tilde{x} + A^{-1}\delta_b \\ ...
2
votes
0answers
38 views

compute the bisecting normal hyperplane between two $n$-dimensional points.

I have two points $\mathbf{x_1}$ and $\mathbf{x_2}$, where $\mathbf{x_i}=\{x^i_1, x^i_2, \ldots, x^i_n\}$. I need to find a normal hyperplane $P$ that goes through the midpoint of $\mathbf{x_1}$ and ...
-1
votes
0answers
22 views

Span and dimension of a basis [on hold]

I have to prove that there does not exist a generating set for $\bf x$ with less of $n$ vectors when $n$ is the dimension of the basis of $\bf x$. Help please!
0
votes
1answer
31 views

Jacobi vs. Gauss-Seidel: convergence

I know that for tridiagonal matrices the two iterative methods for linear system solving, the Gauss-Seidel method and the Jacobi one, either both converge or neither converges, and the Gauss-Seidel ...
0
votes
1answer
26 views

Tridiagonalize matrices with Householder transformation

I know that it is possible to tridiagonalize symmetric matrices by using a Householder trafo. I also found that we can get any matrix to Hessenberg form by using Householder trafos, but I still don't ...
0
votes
0answers
33 views

Integration of ODE equation in Matlab / Octave

I have a system of 8 ODE's where the initial conditions are in matrix form. $\frac{dT}{dS} = H T$ where T at the initial state is the identity matrix. $T(a) = I$ H is a constant 8x8 matrix T is ...
0
votes
0answers
13 views

Is the Hessenberg form of a matrix unique?

I have to calculate the Hessenberg form of an matrix using householder reflectors. For real Matrices I get the same result as the 'hess()' function in Matlab, but for Complex Matrices I keep getting ...
0
votes
0answers
51 views

Alternative to the Gram-Schmidt Procedure for Orthogonalization

I was wondering if there is an alternative to the Gram-Schmidt procedure, which instead of being a successive orthogonalization scheme, would be non-successive (simultaneous)? In other words, is there ...
1
vote
1answer
16 views

Matrices admit a QR decomposition

I just wanted to ask which matrices admit a QR decomposition. I think that all matrices $A \in \mathbb{R}^{m \times n}$ with $m \ge n$ admit a QR decomp. Are these the only ones that have a QR decomp, ...
4
votes
1answer
185 views

Generate arbitrary numerically invertable matrix

I'm designing a unit-test for a matrix inversion function. Currently I make a random matrix as a test case by generating its elements with random numbers uniformly distributed in $[0,1)$. If I ...
1
vote
0answers
25 views

stability of FTCS scheme for parabolic equation

Can you suggest any method for stability analysis of FTCS scheme for the the following parabolic equation ? D.E: $u_{t}=a(x,t)u_{xx}+f(x,t,u)$, $0<x<1$, $0<t<T$, $T>0$ BCs: ...
0
votes
0answers
51 views

Proof of theorem about iterative methods

How do I prove that if $A$ is a tridiagonal (or block tridiagonal) matrix then the corresponding $P_J$ and $P_G$ iteration matrices for the Jacobi and Gauss-Seidel methods satisfy that if $\lambda$ is ...
3
votes
1answer
57 views

3-sigma Ellipse, why axis length scales with square root of eigenvalues of covariance-matrix

This is my first post on math.stackexchange and i am not a mathematician, but i took some undergrad math courses and some grad mathematical modelling courses, so i come with a basic understanding of ...
1
vote
1answer
14 views

Condition number of a matrix bounded from below and above?

Is condition number of an invertible matrix bounded from below? And is condition number always bounded from above for an invertible matrix?
0
votes
1answer
26 views

Prove that Frobenius matrix norm is compatible with the vector norm

Show that, the Frobenius matrix norm $||.||_F$ is compatible or consistent with a vector norm $||.||_2$ , that is, $||Ax||_2 \leq ||A||_F ||x||_2, \forall x \in \mathbb{R}^n$. Where $||A||_F = \sqrt{ ...
0
votes
1answer
28 views

Reentrant constraints in active set algorithm?

Problem definition Supposing you're trying to solve a quadratic program: $$ \min_x f(x) = \frac{1}{2}x^T Q x + c^T x \\ \mbox{s.t} \, \; A x \ge b$$ Where Q is square ($n$x$n$), positive semi ...
0
votes
2answers
96 views

Different method for QR decomposition - is it possible

This method could also possibly be applicable to matrices of higher dimension, but for the simplicity of my question i will only ask it for $2$x$2$matrices. Suppose $A=\begin{pmatrix} a_{11} & ...
0
votes
0answers
12 views

How is this a substitution? Linear algebra transformation matrix misunderstanding

I found the following matrix equation in '3D Surveillance System Using Multiple Cameras', (authors: Ajay Kumar Mishra, Bingbing Ni, Stefan Winkler, Ashraf Kassima) (link here): I don't follow the ...
0
votes
0answers
10 views

find the mean of a collection of the solutions of given linear systems

Suppose one has a group of $k\times k$ square matrices $A_i, i = 1,2..n$, another $k$-vector $b$ is also given. I want to exam the mean of the group of vectors $x_i$ over $i = 1,2...n$ where $A_i * ...
0
votes
1answer
67 views

Finding the smallest max eigenvalues for related matrices?

While messing around with a spectral approach to a graph coloring question, I happened upon a type of problem I hadn't seen before. Suppose you have two symmetric $n$ x $n$ matrices in the form ...
0
votes
1answer
45 views

Unique least square solutions

There is a theorem in my book that states: If $A$ is $m\times n$, then the equation $Ax = b$ has a unique least square solution for each $b$ in $\mathbb{R}^m$. But can we find a counter-example to ...
4
votes
1answer
29 views

Implementing trig functions for dual numbers

I'm curious, how do common trig functions get implemented for dual numbers? One way would be to use the power series definition, but that seems inefficient
1
vote
0answers
21 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 ...
0
votes
0answers
12 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
16 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
13 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
4 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
64 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
40 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
34 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
27 views

resources about sparse global constrainted optimization

Please recommend a good resources (books/articles/software) about sparse global constrained optimization?
0
votes
1answer
50 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
30 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
42 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
27 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
29 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
74 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
45 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
52 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
23 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
69 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
33 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
33 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
28 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
17 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
47 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
43 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 ...