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

learn more… | top users | synonyms

1
vote
0answers
58 views

Saddle point problem (KKT) with block-diagonal matrix

Consider the following saddle point problem originating from an interior-point method algorithm: $$ \begin{bmatrix}\mathbf{H} & \mathbf{A}^{T}\\ \mathbf{A} & \mathbf{0} ...
0
votes
2answers
47 views

Euler method(path s1s2=s2s1)

Given a differential equation $\frac{dy}{dx}=f(x,y(x)), y(x_0)=y_0$. What is the condition for function of f(x,y) such that the result of $y(x_0+S_1+S_2)$ by using Euler forward method, a step size ...
0
votes
1answer
157 views

How do I find transformation matrix with respect to given basis in the domain and/or the codomain, given the transformation in the standard basis?

I´m being given a linear transformation, for which I can find the standard basis in the domain and codomain; but then, the book ask to find the associated matrix related to a new basis for the ...
0
votes
1answer
54 views

An algorithm of solving a non-homogeneous linear equation by random matrices

I'm looking for the proof of the following numerical algorithm. Suppose I want to solve a non-homogeneous linear equation \begin{equation} A x = b \end{equation} The matrix $A$ is non-invertible and ...
0
votes
1answer
45 views

Is it possible to optimize solution of this linear system?

I have a matrix of the form: ...
2
votes
2answers
92 views

How to prove the eigenvalues of tridiagonal matrix?

Assume the tridiagonal matrix $T$ is in this form: $$ T = \begin{bmatrix} a & c & & & &\\ b & a & c & ...
0
votes
0answers
37 views

matrix diagonalization without eigen decomposition, what other ways available?

I have a matrix, $A$ (it may be symmetric or asymmetric). I need to have a diagonal matrix without eigenvalue decomposition, please suggest what others ways are possible? Any new idea would be much ...
1
vote
2answers
77 views

Finding only first row in a matrix inverse

Let's say I have a somewhat large matrix $M$ and I need to find its inverse $M^{-1}$, but I only care about the first row in that inverse, what's the best algorithm to use to calculate just this row? ...
1
vote
1answer
45 views

Solve set of poorly conditioned linear equations in block matrix form

I would like to solve the following set of linear equations where A, B, C and D are each 4x4 matrices. K is then an 8x8 matrix The values in A and D have magnitudes of $\approx 10^{17}$, B has ...
1
vote
0answers
39 views

Write down a linear programming problem

I want to replicate a linear programming problem.I have the following information, for the background." A fuzzy regression analysis with only one independent variable X results in the following ...
2
votes
0answers
39 views

Lagrange multiplier for more than one constraints.

How to minimize $x^TAx$ over the set $D=(x\geq 0, x^TBx=1$ and $(I-A^\dagger A)x=0$), where $A$ is copositive matrix of order $n-1$ and $B$ is strictly copositive matrix of order $n$. If I drop the ...
0
votes
1answer
16 views

$\mathbb{R}^3$ to Planar Subspace Tranform

I'll ask my question three ways to try to maximize my chances of successful communication. I have: a point $P$ in $\mathbb{R}^3$ with coordinates $(P_X,P_Y,P_Z)$ a plane Defined by: a point '$O$' ...
1
vote
0answers
47 views

Solve linear system with matlab

In my problem, $A$ is a $m \times n$ matrix with $m \geq n$ and $\mathrm{rank}(A)= n$. Let $\Gamma$ be the $(m+n) \times n$ matrix defined by : $$ \Gamma = \begin{bmatrix} A \\ \mathrm{I_{n}} ...
3
votes
1answer
80 views

Generalized inverse/Pseudo Inverse

Let $A_{m. n}$ be a matrix with rank $p$ where $p\leq m$ and $p\leq n$. First Question: We need to show that $A$ can be decomposed as a product of two matrices $A=BC$ where $B$ is an $m$ by $p$ and ...
0
votes
0answers
29 views

computing leftmost eigenpair of positive-definite matrix

Let $A$ be an $n\times n$ real symmetric positive-definite matrix. Assume that $n$ is large and that $A$ is dense (i.e. it is not sparse). Question: What is the state-of-the-art algorithmically for ...
0
votes
0answers
46 views

Test for powers method

I have been told that for a normal matrix $A$, the powers method (i.e. computing the succession of Rayleigh quotients for a succession of vectors $z_k=A\cdot z_{k-1}$) can use the following stop ...
3
votes
1answer
133 views

Inverse of a diagonal matrix plus a constant

I am looking for an efficient solution for inverting a matrix in the following form: $D+aP$ where D is a (full-rank) diagonal matrix, a is a constant, and P is a one matrix. This question Inverse of ...
3
votes
2answers
147 views

How to efficiently solve a series of similar matrix equations using the LU decomposition

This is the problem I'm dealing with: Let $\sigma_1,\dots,\sigma_n \in \mathbb{R}$ and $b_1,\dots,b_n$ be column vectors of length $n$. Consider the system $$ (A - \sigma_jI)x_j = b_j, \quad ...
0
votes
1answer
26 views

Function from one Null space to Another

Suppose a single vector space over $R$ of degree $n$, and two matrices $A, B$ of arbitrary row size, but col size $n$, s.t. their individual null spaces are linear subspaces of this vector space. Is ...
0
votes
0answers
39 views

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

I am attempting to make a Gaussian Elimination solver for systems of linear equations that contain less than 100 equations. I have roughed out a method for creating and filling in the diagonal of a ...
0
votes
4answers
187 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
0answers
31 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
81 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 ...
0
votes
1answer
244 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
141 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
47 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
69 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
80 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
33 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, ...
5
votes
1answer
203 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
102 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
102 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 ...
4
votes
1answer
327 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
25 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
210 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
40 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
105 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
33 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
1answer
81 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
96 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
2answers
56 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
53 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
26 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
43 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
23 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
36 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
68 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
47 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
76 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
1answer
86 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 ...