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

learn more… | top users | synonyms

1
vote
0answers
24 views

Meaning of singular Jacobian and workarounds to Newton's method

I'm currently working with Galerkin's method to solve differential equations and I have to retrieve unknown coefficients for the truncate expansion. This is just to set the background for why I need ...
1
vote
0answers
17 views

LU Decomposition for the solution of two linear systems

Let's say I have the following linear system: \begin{equation} \left[ \begin{array}{cccc} S&&L^{T}&&A^{T}&&0\\ L&&0&&0&&0\\ ...
1
vote
0answers
16 views

the Gauss-Jordan algorithm requires how many multiplications/divisions and add/subtractions

I am trying to show this following result. The Gauss-Jordan algorithm requires $\frac{n^3}{2}+n^2-\frac{n}{2}$ multiplications/divisions and requires $\frac{n^3}{2}-\frac{n}{2}$ ...
1
vote
0answers
50 views

Does this function have a unique fixed point?

Consider the following equations in fixed-point form: $$\mathbf{x}=F(\mathbf{x})=[f_1(\mathbf{x}),f_2(\mathbf{x}),\cdots,f_n(\mathbf{x})]^T$$ where the function $f_i$ is defined as ...
1
vote
0answers
13 views

Speed of pseudo-inverse (with possibly ill-conditioned matrices)

I am computing the pseudo-inverse of several matrices of identical size $m \times n$ . However, computation (e.g. with the LAPACK pinv) seems to be much slower in some cases (5 to 10 times slower). ...
1
vote
0answers
29 views

Strictly diagonal matrix

Suppose that matrix $A$ is strictly diagonally dominant, show that $||A^{-1}||_{\infty}\leq[min(|a_{ii}|-|\sum_{i\neq j}^n a_{ij}|)]^{-1}$.
1
vote
0answers
20 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
29 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 ...
1
vote
0answers
35 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}} ...
1
vote
0answers
53 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: ...
1
vote
0answers
40 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
17 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 ...
1
vote
0answers
15 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. ...
1
vote
0answers
38 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$ ...
1
vote
0answers
35 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 ?
1
vote
0answers
36 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 ...
1
vote
0answers
34 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 & ...
1
vote
0answers
48 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 ...
1
vote
0answers
47 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
41 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, ...
1
vote
0answers
36 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 ...
1
vote
0answers
32 views

Influence of preconditioning on degenerate eigenvectors

I'm using a hierarchical decomposition of a sparse matrix $A$ as suggested here. I find that the method essentially finds eigenvectors using the QR algorithm. $A$ has some eigenvalues with ...
1
vote
0answers
76 views

Newton's method for multidimensional functions

Can Newton's method be used to find the root of a function f : $\mathbb{R}^n\to\mathbb{R}^m$. Can anyone provide a proof for this? (I have checked the method of solving system of equations with ...
1
vote
0answers
40 views

Change in Singular Value Decomposition of a matrix on addition of a single row

Given that I know the svd decomposition of a matrix, is there any way to compute the svd decomposition of the matrix obtained by adding a single row to the original matrix? Is there any relation ...
1
vote
0answers
51 views

If symmetric matrix in a least-square deconvolution problem positive definite?

I want to apply Gauss-Seidel method in a least square deconvolution problem. The convolution of two vectors is written in: $h * x = z$. $$z(n) = \sum_{i=0}^{N-1}h(i)x(n-i)$$ It is a linear transform ...
1
vote
0answers
56 views

Numerical algorithm to solve quadratic eigenvalue problem.

Given the equation $$-4 \left(a^2+a (n-1) (2 t^2-1)\right) \left(\sum _{i=0}^n \alpha_i t^{2 i}\right)^2 \\ +\frac12 \left(\sum _{i=0}^n \alpha_i t^{2 i}\right) \left(t \left(8 a (t^2-1)+1\right) \sum ...
1
vote
0answers
45 views

Kalman Filter Predict Update of LDL Decomposition of a Covariance Matrix

From the state predict equation: http://en.wikipedia.org/wiki/Kalman_filter# $$P_{n+1}=AP_nA^T + Q$$ Suppose the $LDL^{T}$ ( http://en.wikipedia.org/wiki/Cholesky_decomposition#LDL_decomposition_2 ) ...
1
vote
0answers
22 views

Algorithm for finding only the $k$-th singular vectors

I know that we have truncated SVD that can compute the first say $k$ largest singular values (and corresponding singular vectors). However, I'd like to know if there is an algorithm that can find only ...
1
vote
0answers
49 views

Best way to solve specific block-tridiagonal linear system (10000x10000 and larger)

To provide more context, this system came from energy balance equation on a mesh with (n,m) nodes in each direction. It's a linear system that looks like this (size of system in blocks n = 4, size of ...
1
vote
0answers
36 views

Solving a linear equation with a moderatly sparse 1000000*1000000 symmetric matrix

I've got a linear equation $A_{n*n}\cdot x=1_n$, where $n=1000000$ and $A$ is symmetric with approx $1000$ nonzero entries in each column and row. What would be the best numerically stable algorithm ...
1
vote
0answers
26 views

Simultaneous iteration of Symmetric Matrices

Given a Matrix $A$ we can use Simultaneous iteration(Using power iteration on all columns simultaneously) to compute the d biggest eigenvalues. Now this method will give you the biggest eigenvalues, ...
1
vote
0answers
32 views

Gerschgorin Theorem singularity proof

I know how to prove the Gerschgorin Theorem but how exactly would one show that there are no values of $\mu$ s.t. $\mu<0$ for which $A-\mu B$ is singular where $$ A= \begin{bmatrix} ...
1
vote
0answers
24 views

Gaussian Elimination theoretical question

You know how Gaussian Elimination can be broken up into a sequence of L-U premultiplications right? Suppose that there is a matrix $A=a_{i,j} : j=1,...,n$ is an $n × n$ real matrix such that ...
1
vote
0answers
57 views

Least squares of symmetric positive semidefinite matrices

What's the best (in terms of computation time and numerical robustness) way to find the least squares solution of $$Ax = b$$ if $A$ is symmetric and positive semi-definite? If $A$ were symmetric and ...
1
vote
0answers
13 views

Finding eigenvalues in a region

I have an eigenvalue problem (of a very large (n~1000000) but sparse complex system) wherein I need to determine all the eigenvalues in a certain region(a rectangle) in the positive half plane. I am ...
1
vote
0answers
44 views

Representation of Uncertainty in linear systems

I have a linear uncertain system represented by a family of models: $\dot{x}=A_ix$,$i=1,\cdots,N$ I want to represent the system as: $A_i=A_0+B\Delta_iC$ subject to the condition that $\lVert ...
1
vote
0answers
70 views

Algorithm to determine matrix equivalence

I'm a physicist who's not particularly good at linear algebra so please accept my apologies if this is standard textbook stuff that I'm just unaware of. I have two real rectangular matrices $A_{mxn} ...
1
vote
0answers
84 views

is it possible to generate a unique number given a set of N integers regardless of their permutation?

I need to efficiently compute an "id" for a set of N integers, the id needs to be unique if any of the numbers is different from some other set. At the same time the id needs to be the same if the ...
1
vote
0answers
52 views

How can solve this differential equation (third equation )?

How can I solve this differential equation? $$ \frac{dy}{dx}=\sqrt{\frac{A}{y}+\frac{B}{y^2}+\frac{C}{y^4}+\frac{D}{y^5}+\frac{1}{(\frac{1}{y}+\frac{3}{y^2})^2}} $$ where $A,B,C,D$ are constants.
1
vote
0answers
105 views

Proof-finding: Power iteration and complexity of the Rayleigh quotient

I'm searching for a proof for this theorem: \begin{align} |\lambda^{(k)}-\lambda_1| = \mathcal{O}\Big(\Big|\frac{\lambda_2}{\lambda_1}\Big|^{2k}\Big) \end{align} where \begin{align} \lambda^{(k)} ...
1
vote
0answers
63 views

Solving for A in the system Ax = 0

Consider the system of linear equations $A x = 0$ where $A$ is a $K \times M$ matrix of reals and $x$ is an $M \times 1$ vector of reals. The matrix $A$ is unknown but we can generate $x$s that ...
1
vote
0answers
28 views

The least-squares solution for interval data

I would like to solve the least-squares for $\mathbf{Ax} = \mathbf{y}$ with some values in $\mathbf{A}$ and also in $\mathbf{y}$ are interval-valued numbers. In a more detail, e.g.,: $$ ...
1
vote
0answers
151 views

Solving linear system of equations using Successive Over-Relaxation

I was solving a system of linear equations with SOR. I used different values of relaxation factor (w) for the different runs. I found that for all w > w' (1 < w' < 2), the error is the result ...
1
vote
0answers
121 views

Orthogonal Procrustes Problem

The classical orthogonal Procrustes problem concerns finding the matrix $\Omega$ which minimizes $||A\Omega-B||_{F}$ subject to $\Omega'\Omega=I$, with A and B known matrices. Let A be the identity. I ...
1
vote
0answers
69 views

$F(x)=Ax+b$ is a contraction mapping

I want to proof that $f(x)=Ax+b$ with \begin{align} A = \begin{bmatrix} 0 & -\frac{1}{8} & \frac{1}{4} \\ 0 & \frac{1}{3} & 0 \\ -\frac{1}{2} & -\frac{5}{22} & \frac{3}{4} ...
1
vote
0answers
82 views

Applications of Numerical methods

I'm in a course of Numerical Methods and part of an assignment is find an article about an application of numerical methods, explain this article and present a program (in matlab/octave) that ...
1
vote
0answers
67 views

How to condense a matrix to a vector

I'm not an experienced person in mathematics and this might either sound like a trivial question or a stupid one. However, this problem arose to me when I was writing a program. Following is my ...
1
vote
0answers
60 views

Reformulating objective function of canonical correlation analysis

Given two column vectors $X = (x_1, \dots, x_n)'$ and $Y = (y_1, \dots, y_m)'$ of random variables with finite second moments, canonical-correlation analysis seeks vectors $a$ and $b$ such that the ...
1
vote
0answers
41 views

Matrix computing

Given an $n$-vector $x$, show that floating-point computation of the Householder vector $v$ such that $P x = (I − 2vv^{T} )x = \pm\left\|x\right\|_{2}e_{1} $ gives a forward stable result $v^{\prime}$ ...
1
vote
0answers
115 views

Matrix-valued expansion in spherical harmonics

I am seeking a clever solution to the following problem. Given $$X(\theta,\phi) = exp(-iA(\theta,\phi))\; B\; exp(+iA(\theta,\phi))$$ with the square, Hermitian matrix $A$: $$A(\theta,\phi) = A_{0,0} ...