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

learn more… | top users | synonyms

1
vote
0answers
13 views

Enforcing additional constraints in linear equation

In a finite element context, I come up with a sparse "stiffness matrix" $A$ and a corresponding RHS $b$. The goal is now to solve $$Au = b$$ Where $u$ is a coefficient vector of the solution. Now I ...
1
vote
0answers
35 views

Solving System of Linear Equations

These are the two known equations: $$\frac{(I_2+I_3)-(I_1+I_4)}{I_1+I_2+I_3+I_4} = \frac{2x}{L}$$ $$\frac{(I_2+I_4)-(I_1+I_3)}{I_1+I_2+I_3+I_4} = \frac{2y}{L}$$ where I know the values of $(x,y,L)$. ...
1
vote
0answers
51 views

SVD of a block partitioned matrix

Given a block partitioned matrix $\boldsymbol{A}$ $$ \boldsymbol{A} = \begin{bmatrix} \boldsymbol{A}_{1,1} & \boldsymbol{A}_{1,2} & \cdots \\ \boldsymbol{A}_{2,1} & ...
1
vote
0answers
309 views

Really confused about LU decomposition and Doolittle algorithm

I'm really confused about the Doolittle algorithm, so I need some help. At the end of the description at wikipedia, it says It is clear that in order for this algorithm to work, one needs to ...
1
vote
0answers
65 views

Question on the uniqueness of LU decomposition

Let $A \in \mathbb{K}^{n \times n}$ a matrix, and suppose that we can run the Gaussian elimination on $A$ without row or column interchange, so there exist the $LU$ decomposition of $A$. We define ...
1
vote
0answers
86 views

Using Cholesky factorization to solve the system AXA=B

I have been given a problem of solving X, which is an unblurred image, in the system: $$B = A X A \iff X = A^{-1} B A^{-1}$$ Where the matrix A describes the blurring of an image and the matrix B is ...
1
vote
0answers
56 views

Least-squares solution to a transformation between coordinate frames

Suppose I have four coordinate frames in 3D space: A, B, X and ...
1
vote
0answers
37 views

LU-factorisation of a square matrix

I need to show that the following matrix cannot be factor into the product LU. \begin{equation} A=\begin{bmatrix}1&2&-1\\2&4&0\\ 0&1&-1\end{bmatrix} \end{equation} I did the ...
1
vote
0answers
45 views

What's the point of 1-norm matrix estimation? Why not brute force?

Calculating (brute-force) 1-norm of a square matrix should take $O(n^2)$ operations, with a small factor involved. Apparently, there is an algorithm (link) for estimating 1-norm that takes $O(n^2 t)$ ...
1
vote
0answers
36 views

Is it better to compute $A^tA$ once and then $Ax$ several times or compute $y=Ax$ and then $A^ty$ every time?

So I have this algorithm which given a matrix $A$ it assigns $A=A^tA$ outside the loop and then on the algorithm loop it solves multiple instances of $Ax$ for different $x$s, (meaning that it's ...
1
vote
0answers
53 views

matrix with positive diagonal elements

I was wondering if a symmetric matrix with positive elements only in the diagonal (negative elsewhere) is any special beside the symmetry. Thanks in advance
1
vote
0answers
70 views

Rayleigh quotient ($|r(q)-\lambda|=O(||q-x||_2^2)$ ?)

how to show $|r(q)-\lambda|=O(||q-x||_2^2)$ $r(q)=q^*Aq/(q^*q)$ and $\lambda$ is an eigenvalue, A is a Hermitian matrix. x is the unit eigenvector corresponding to $\lambda$. and q is a unit vector. ...
1
vote
0answers
232 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
25 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
86 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
65 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
27 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
53 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
80 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
165 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
64 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
38 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
31 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
58 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
54 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
54 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
43 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
61 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
159 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
104 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
61 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
34 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
133 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
137 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
135 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
70 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
92 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
33 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
45 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
37 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
45 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
32 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
181 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
24 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
49 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
117 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
91 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
54 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
196 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
84 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 ...