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

learn more… | top users | synonyms

2
votes
0answers
98 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 ) ...
2
votes
0answers
357 views

Standard symmetric tridiagonal matrix Eigenvalue decomposition algorithm?

Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm (here). I need to code this on C++ for my personal project. This algorithm involves the eigenvalue ...
2
votes
0answers
79 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
2
votes
0answers
36 views

Smallest set of Liner equations, which exactly fit a set of points

I have a set of 2-d points,(it can be of any arbitrary dimension n). I want to find the minimum set of straight lines(linear equations) which exactly passes through the given 2-d points (unlike ...
2
votes
0answers
70 views

Find the eigenvector with maximum overlap

Given a large symmetric matrix $A$, there are methods to find the largest or smaller eigenvalue, or the eigenvalue closest to some initial value. Is there any method to find the normalized ...
2
votes
0answers
56 views

linear algebra formulation help

I asked this on mathoverflow as well and apologies for cross-posting. I am trying to compute this so-called bending energy matrix. The bending energy of a thin plate in 3D is given by: $$ BE = \int_0^...
2
votes
0answers
166 views

Finding generalized eigenvalues with linear constraints

I have a generalized eigenvalue problem $$Mx = \lambda Bx$$ with the additional constraint that $Cx=0$, where $M$ and $B$ are positive-definite and $C$ is a sparse and rectangular. Is there a simple ...
2
votes
0answers
26 views

Nontrivial Matrix-estimate

I try to proof the following estimate: \begin{align} h' W^{-1} H W^{-1} h \geq c h' H h \qquad c>0, \qquad\qquad (1) \end{align} where $h\in\mathbb{R}^{K-1}$ and $W,H\in\mathbb{R}^{(K-1)\times(K-1)...
2
votes
0answers
234 views

How to generate a random matrix which have given singular values?

I know one method: generate a random matrix, apply SVD decomposition, modify singular values, and then multiply those matrices back together. However, I'm wondering how random this method is. Since ...
2
votes
0answers
84 views

Inverses of the sums of all possible subsets of a set of symmetric and positive definite matrices

I have a set of $c$ matrices $A_1 ... A_c$ which are all symmetric and positive definite. I would like to calculate the inverses of all the possible sums, i.e. $(A_1+A_2)^{-1},(A_1+A_3)^{-1},(A_2+A_3)...
2
votes
0answers
1k views

Least Squares “analytic expression” for fitting a 2D quadratic function to measurements

I have n scattered elevation measurements: $ \{x_i,y_i,z_i\}_{i=1..n} $ that I want to fit a quadratic function to: $ z = ax^2 + by^2 + cxy + dx + ey + f$. The problem can be written as a vector ...
2
votes
0answers
81 views

What is the significance of the matrix in the LAPACK logo?

This is the LAPACK linear algebra library logo: What is the significance of this matrix?
2
votes
0answers
108 views

Determinant error bound is better than norm bound for matrix product

In by textbook on numerical algebra, it states that for a numerical matrix product the error bound: $|A B - \hat{A} \hat{B}| \le c|A| |B|$ is a stronger expression than $\|A B - \hat{A} \hat{B}\|_{\...
2
votes
0answers
50 views

maximal m-elements of the matrix inversion

Suppose the $n\times n$ matrix $A$ is invertible, and all its elements are between 0 and 1. The existing matrix inversion operation of $A^{-1}$ will take $O(n^3)$ time. Now I just want to find the ...
2
votes
0answers
178 views

Nearest point to a convex polytope

I am looking for fast, memory-efficient computational algorithms to solve the following problem: Minimize: $||x - x*||_2^2$, subject to constraints $A x = a, B x <= b, l <= x <= u$, where $...
2
votes
0answers
65 views

Customising force-directed graph layout

I would like to implement a variant of the force-directed graph layout where some nodes are constrained to moving only along a predefined curve (e. g. circle). I looked at some implementations using ...
2
votes
0answers
171 views

Orthonormal Matrix weighted regression

$Q$ is a rectangular matrix with orthonormal columns. A linear system composed of $$Qx= b$$ is really easy to solve as: $$Q'Q=I$$ hence: $$x=Q'b$$ Given that $Q$ is orthonormal can this be used to ...
2
votes
0answers
220 views

$l^1$ norm estimate for inverse of Vandermonde matrix

As title, I would like to know the known upper bound for the $l^1$ norm for inverse of Vandermonde matrix. A quick search gives this paper by Gautschi 40 years ago, but it deals with the infinity norm ...
2
votes
0answers
57 views

Solution to pertubed linear system

Suppose one has the following system of linear equations $$(A + \Delta A) x = b$$ where $A$ and $\Delta A$ are large sparse matrices and $\Delta A$ is "small" compared to $A$, furthermore vector $x$ ...
2
votes
0answers
162 views

Showing that the least-square method minimizes error

Assume that the relation between temperature and time is defined as follows: $$T = A^kC$$ We can find parameters $A$ and $C$ using the least-square method. The given relation is not linear, but we can ...
2
votes
0answers
66 views

commuting a LU factorisation

Consider the permutation matrix $P= \begin{pmatrix} 0 & \cdots & 0 & 1 \\ 0 & \cdots & 1 &0 \\ \vdots & \ddots & \vdots & \vdots \\ 1 & \cdots &...
2
votes
0answers
202 views

Check for Ill Conditioned matrix

How can I efficiently check if a tridiagonal system with 1's in diagonal is ill-conditioned or not ? The common way is to get the ratio of largest and smallest singular values and see if its greater ...
2
votes
0answers
27 views

Re-calculate solution after altering some elements in a linear system

Problem I have a linear system: $$ Mx = b $$ $M$ is like a Band Matrix. And assume I have a solution $x_{init}$ at beginning. There will be some operations which are going to alter some elements in ...
2
votes
0answers
82 views

Spectral/ Eigen-Value solution with a linear constraint?

Is there a spectral or eigen-value solution to finding $X$ such that $Tr(CX^TMX)$ is minimum for a symmetric matrix $C$ and a p.s.d matrix $M$. Also there is a linear constraint on the minimization ...
2
votes
0answers
144 views

The norm of the matrix

This problem is in Trefethen'book Numerical Linear Algebra Suppose the $m\times n$ matrix $A$ has the form $A=\begin{pmatrix}A_1\\A_2 \end{pmatrix}$ where $A_1$ is a nonsingular matrix of dimension ...
2
votes
0answers
88 views

Need little hint to prove a theorem .

I have an iterative method \begin{eqnarray} X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots \end{eqnarray} with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
2
votes
0answers
3k views

What is the algorithm for LU factorization in MATLAB?

What is the algorithm for LU factorization in MATLAB, i.e. [L,U] = lu(a)? After searching for many examples and trying to compare the result with MATLAB, they are ...
2
votes
0answers
186 views

(Experimental) Can it be shown that this extension of the secant-interpolation has quadratic convergence?

Background: I needed some efficient but simple interpolation-methods aside of Newton's iteration because I want to have it in contexts, where the derivative of a function is not always known. So an ...
2
votes
0answers
1k views

QR with column pivoting

Golub and van Loan's algorithm 5.4.1 for QR factorization is suitable as a rank revealing algorithm. The results are R, Q with the subdiagonal elements stored in "factored form" and the column ...
1
vote
0answers
23 views

Why does power iteration generate almost dependent vectors?

On the Wiki page for Krylov subspaces: https://en.wikipedia.org/wiki/Krylov_subspace it states given a matrix $A$ and vector $b$, that the vectors $b, Ab, A^2b, A^3b, ...$ "soon become almost linearly ...
1
vote
0answers
23 views

What is the opposite of “sparsity” in a matrix?

If a sparse matrix has only 1% non-zero entries, I find it weird to speak of "1% sparsity". In particular, "increasing sparsity" goes along with a smaller percentage of non-zero entries, so this is ...
1
vote
0answers
27 views

Directly solving non-square subproblem of linear system

I have a large sparse linear system $$\begin{pmatrix} A & B\\ C & D \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} f \\ g \end{pmatrix}$$ which ...
1
vote
0answers
31 views

Sensitivity of Eigenvalues with invertibte matrix

Let $A$ a matrix having a set of eigenvectors $\{v_1,\ldots,v_n\}$ linearly independent with $\{\lambda_1,\ldots,\lambda_n\}$ eigenvalues associated. Let $\lambda$ eigenvalue of the perturbed matrix $...
1
vote
0answers
37 views

Create a matrix of four-dimensional space rotate counterclockwise by the angle π / 3 around the plane

Create a matrix of four-dimensional space rotate counterclockwise by the angle $\frac{π}{3}$ around the plane \begin{cases} x − y + t = 0,\\[2ex] y + z + t = 0 \end{cases} on the basis of unit ...
1
vote
0answers
47 views

Dual Norm proof

Let $\|.\|$ denote any norm on $C^m$. The corresponding dual norm $\|.\|'$ is defined by the formula $\|x\|' = sup_{\|y\|=1}|y^*x|$. (a)Prove that $\|.\|'$ is a norm? (b) Let $x, y \in C^m $ with ...
1
vote
0answers
16 views

why does matrix balancing improve the linear systems condition number of the eigenvector matrix?

Matrix balancing or diagonal scaling, where at each iteration we choose a diagonal matrix so that the row and column norms are approximately equal (Osborne, 1960, Parlett and Reinsch, 1969, many ...
1
vote
0answers
5 views

Fast square of a row-stochastic matrix

I would like to implement the square $M^2$ of a row-stochastic matrix $M$. Running time is critical. Are there any known algorithms that exploit the special nature of $M$ and are faster than the usual ...
1
vote
0answers
27 views

Numerical stability of computational results

Let z be a function of a finite number of variables i.e. z=f(a,b,c,...). If we have the mathematical formula connecting z and the variables, we can determine how the value of z varies with a change ...
1
vote
0answers
43 views

Why is it difficult (and not precise) to compute the rank of large matrix numerically?

I have a general question. I have a large square matrix ($n> 1000$) and it is needed to compute the rank of this matrix. I am reading that the computation of the rank for large matrices, can make ...
1
vote
0answers
30 views

Eigenvalue equation and the diffusion equation

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system $\...
1
vote
0answers
30 views

Spectral relaxation of k-means clustering

I am working on a presentation on Spectral relaxation of k-means clustering (http://papers.nips.cc/paper/1992-spectral-relaxation-for-k-means-clustering.pdf) and I am a bit stuck. I understand ...
1
vote
0answers
16 views

Is it possible to construct a consistent unstable one step method of order 2? why?

Is it possible to construct a consistent unstable one step method of order 2? why? I think the answer is no but I have no clue to prove it. Can anyone give me some explanations? Thank you in advance ...
1
vote
0answers
21 views

Is there a way to find if there exists a solution such that all the variables in a system of linear equations are either 0 or 1 in P time?

Note this is different from Binary Integer Programming as it does not involve inequalities. An example would be a+b = 1. A solution would be a = 0, b = 1. I just want 1 solution, or even if there ...
1
vote
0answers
28 views

Numerical issues with matrix exponential for diagonalizable matrix

I am learning about computation of matrix exponentials, and have come across the technique: $$ e^A = U \operatorname{diag}(e^{\lambda_1}, e^{\lambda_2}, \ldots, e^{\lambda_n}) U^{-1}$$ Where the $\...
1
vote
0answers
15 views

$Q$ is perfectly conditioned with respect to the 2-condition number.

Show that if $Q$ is orthogonal, then: $||Q||_2 = 1$, $||Q^{-1}||_2=1$, and $\kappa_2(Q)=1$. Tell me if I'm wrong but, I'm at if $||QQ^T||_2 = ||I||_2$ then $||QQ^T||_2 = 1$ which implies that $...
1
vote
0answers
34 views

Is this a correct way to approximate a derivative

I have some function $S(\hat y)$ which I want to approximate its derivative with respect to a vector. It's a tad complicated, I'll try and explain. $S$ is a function of $\hat y$ only, but $\hat y$ is ...
1
vote
0answers
14 views

How to determine if an algorithm converges for solving Ax = b in practice?

Suppose I am using iterative refinement. I am updating the solution $$x^{(k+1)} = x^{(k)} +p$$ where $Ap = b - Ax^{(k)}$. If $A$ is ill-conditioned, then we can not simply use residual norm or the ...
1
vote
0answers
35 views

What is the function of the pivot index vector in Gauss Jordan Elimination with full pivoting?

In numerical recipes, on page 39 (page 4 of the pdf) the following algorithm has been suggested for finding a pivot: ...
1
vote
0answers
52 views

Dynamically equivalent of numerical solution of $y' = f(y)$.

Consider an autonomous system $y' = f(y)$ and a fixed step size $h$. a) Show that the trapezoidal method applied $N$ times is equivalent to applying first half a step of forward Euler, (i.e forward ...
1
vote
0answers
34 views

Galerkin formulation of 1D linear Schrodinger equation

I am interested in the weak (Galerkin) formulation of the 1D Schrodinger equation: $i u_t−\beta u_{xx}=0$ and $u(x,0)=u_0(x)$. As usual, we do integration by parts which yields: $i (u_t,v)+\beta (...