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

learn more… | top users | synonyms

0
votes
0answers
22 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\ ...
0
votes
0answers
9 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 ...
0
votes
0answers
41 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
43 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
0answers
47 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 ...
0
votes
0answers
20 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 ...
0
votes
0answers
36 views

Efficient Factorization for Family of Matrix Equations

I am looking for an efficient solution to the following problem $$ A+\lambda I = b \tag{1} $$ where $A\in\mathbf{S}^{n}$ is a symmetric matrix with nonzero eigenvalues, $b\in\mathbf{R}^n$ is fixed, ...
0
votes
0answers
40 views

System of linrar equations and condition number

The relative error of the solution of a system of linear equation $Ax=b$, for any natural norm $\|\cdot\|$ is bounded by $$ \frac{1}{\| A\| \|A^{-1} \|} \frac{\|r\|}{\|b\|} \le \frac{\|e\|}{\|x\|} \le ...
0
votes
0answers
30 views

What is the largest (dense, real, symmetric) random matrix I can diagonalize on a computer?

I have read that 10.000x10.000 is no problem for LAPACK or similar routines. I would like to know if N=20.000 or 40.000 is possible. EDIT: I don't know if it is relevant, but the matrix is positive ...
0
votes
0answers
39 views

Strange Convergence of SOR/Gauss-Seidel

I am having trouble with the convergence of my Gauss-Seidel/SOR method. The matrix $A$ in $Ax=y$ seems to be positive-(semi)definite. Its eigenvalues are: However, the method (SOR) improves the cost ...
0
votes
0answers
40 views

How to find a transformation matrix T?

(1.) Suppose there is matrix C of dimension "p by n" where p is less then n i.e. p I want to know is there any particular way exist to find transformation matrix T of dimension "n by n" such that ...
0
votes
0answers
26 views

Orthogonal polynomials induction proof

I tried writing this all out but cannot seem to get anything sensible. Basically I want to prove that assuming w(x) is the weight function of a Gram Schmidt orthogonalization process and w is an ...
0
votes
0answers
41 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 ) ...
0
votes
0answers
19 views

Maximal angle between kernel of rows of a matrix

Consider a matrix with 2 columns $$ \begin{pmatrix} a_1 & b_1 \\ a_2 & b_2 \\ a_3 & b_3 \\ \vdots & \vdots \end{pmatrix} . $$ To each row $(a_i \;\;\; b_i)$, one draws the kernel ...
0
votes
0answers
28 views

Not enough memory for GMRES

After realizing that Gauss-Seidel is extremely slow for my simulation, i wanted to try GMRES and luckily found the C++ code here without diving into the theory. The size of the matrix in my case is ...
0
votes
0answers
54 views

Francis Algorithm (Implicit QR Algorithm)

In Numerical Analysis, we are touching upon QR and Francis Algorithm. I understand that for Francis's Algorithm, we reduce the matrix to its upper Hessenberg form using Householder transform. What I ...
0
votes
0answers
51 views

Upper Hessenberg Form

I am given a matrix. I would like to reduce it to its upper Hessenberg Form. We are discussing eigenvalue computations in Numerical Analysis and the textbook just gives the algorithm for it without an ...
0
votes
0answers
43 views

Minimizing a vector constrained to a set

Sorry if this is wordy or over-complicated, I'm not sure how to isolate the problem any more than I have below without losing important context: I'm trying to implement a coordinate block descent ...
0
votes
0answers
45 views

QR Algorithm with Shifts Question

Why must QR Algorithm with Shifts make no progress when applied to this n x n matrix? (attached as image). Also, if a matrix A is orthogonal in a QR factorization, will R be tridiagonal? How would ...
0
votes
0answers
36 views

cubic B-spline interpolation function

I read that the B-spline basis functions are the follows: $B_0(x)=(1-x)^3/6$ $B_1(x)=(3x^3-6x^2+4)/6$ $B_2(x)=(-3x^3+3x^2+3x+1)/6$ $B_3(x)=x^3/6$ The cubic b-spline interpolation function it ...
0
votes
0answers
66 views

convergence for symmetric, positive semi-definite operator

Assume $u$ is a vector in the Euclidean space $\mathbb{R}^N$, $||u||=\sqrt{\langle u, u\rangle}$, where $\langle u, v\rangle = \sum_{i=1}^N u_i v_i$. I have that $||u^{k+1}-u||\leq ||I - c ...
0
votes
0answers
63 views

Numerical Linear Algebra- Proof for the Backward stability of inner Product?

I know that inner product is backward stable through various sources but to prove this statement is which I'm not aware of...if someone could help me with that that would be great. ...
0
votes
0answers
24 views

Iteratively solve linear equations with rank-1 updates on LHS and RHS

What is the best way to iteratively solve updating equations of the form $$ Ax=b $$ $$ (A+c_1v_1^\intercal)x_1=b+ \alpha_1 d_1 $$ $$ (A+c_1v_1^\intercal+c_2v_2^\intercal)x_2=b+\alpha_1d_1+\alpha_2d_2 ...
0
votes
0answers
56 views

Rank and solvability of a matrix

I am working with linear complementarity problems (LCPs) which look for a solution $\mathbf{x} \in \mathbb{R}^{n}$ in the form $$ \begin{matrix} \mathbf{x} & \geq & 0 \\ ...
0
votes
0answers
19 views

need to determine weights so that quadrature formula holds

Let $l$ be an interval on the real axis, $t_1,...,t_n$ be distinct $n$ points, then there exists n numbers $m_1,...,m_n$ such that the quadrature formula, $\int_l p(t)dt = m_1p(t_1) + ... + ...
0
votes
0answers
55 views

Expressing rank condition of a matrix in terms of its elements

Let $x \in \mathbb{R}^{n}$, define $X = xx^{T}$. I have an optimization problem with some linear constraints and few quadratic constraints, and I have to solve for $x$. Using $X$ as the unknown ...
0
votes
0answers
30 views

Find the Cholesky Factorization of the matrix A

Just came from my Numerical Analysis midterm. There were 3 questions on it, trying to check my solutions to estimate my grade. Find the Cholesky of $$A = \begin{pmatrix}25 & 15 & -5\\15 & ...
0
votes
0answers
9 views

Predict values of some numerical vectors by using other numerical vectors with all these vectors in the same vector set

I need to solve a problem about predicting values of some numerical vectors by using other numerical vectors with all these vectors in the same vector set, which is generated by one or more black box ...
0
votes
0answers
19 views

How to go from linear “equality-constrained” least squares (LSE) to linear “less-equality-constrained” LSE

I am trying to figure out how to pass from one problem to other. The linear equality-constrained least squares problem can be solved using a generalized RQ factorization (lapack solves this using ...
0
votes
0answers
26 views

Matrix conditioning with one degree of freedom

Given a not so well conditioned, NxK, N>>K matrix A with a certain structure. I have just one degree of freedom: I can multiply each row with a different factor. In formula: $$ \mathbf{B} = ...
0
votes
0answers
39 views

algorithm to separate the roots of a polynom

I need an algorithm to separate the roots of a polynom. The degree of the polynom is n (10 < n < 20) and the polynom has the same number of roots as it's degree. All roots are real. I need to ...
0
votes
0answers
15 views

Singularity check for Homographies

I know that the standard singularity check for a matrix represented in some finite-precision format (IEEE-754 or whatnot) is "the matrix is singular if the reciprocal of the condition number of the ...
0
votes
0answers
17 views

Is any method which allows segmentation of long diagonalizing procedures?

This is a question for a smarter way of numerical computation. When I diagonalize a certain type of Vandermonde-matrices in Pari/GP ("mateigen(M)"), for instance of size 16x16 then this can be ...
0
votes
0answers
54 views

(Numerical) Cholesky Decomposition of a Product of Matrices

Let $E$ be a symmetric positive definite matrix and let $O$ be an orthonormal matrix i.e. $O^{T}O=I$. Let $chol(A)=L$ such that $A=LL^{T}$ i.e. $chol(.)$ is the operation that returns the lower ...
0
votes
0answers
54 views

what is the meaning/characteristics of the component-wise product of right and left eigenvectors.

I have a generic, but seemingly simple question : what is the meaning/characteristics of the component-wise product of right and left eigenvectors (for the same eigenvalue of course) ? let's call ...
0
votes
0answers
51 views

Tridiagonal Gaussian Elimination: Band Storage

I was given this algorithm for Tridiagonal Gaussian Elimination: Band Storage for i = 2:N if W(3,i-1) is zero error('the matrix is singular or pivoting is required') end m = W(4,i)/W(3,i-1) ...
0
votes
0answers
50 views

Least squares problem where rows are multiplied by a factor

I want to solve the following linear system in least squares sense: $Ax = b$ Where $A$ is a sparse matrix which has more rows than columns. To solve it in least squares sense I would need to solve ...
0
votes
0answers
28 views

Doubts on Conjugate and Biconjugate Gradient Method

I am not able to prove that $r^t_iAd_j=0$ for $j\neq i-1$, given $r^t_i$ the $i$-th residual $b-Ax_i$ and $d_j$ the $j$-th $A$-conjugate direction ...
0
votes
0answers
131 views

Solve system of equations AXB = 0

Is there a common approach to solve a system of linear equations in a form $A^TXB = \bf{0}$? Where $A$ and $B$ are known matrices and $X$ is an unknown matrix. This seems simple enough, there should ...
0
votes
0answers
60 views

Cholesky decomposition using Newton-Raphson

Hi I'm trying to do an alternative algorithm for the Cholesky factorization, which factorizes a symmetric pos. def. matrix $A=R^TR$ where $R$ is upper triangular. I'm curious what happens if you solve ...
0
votes
0answers
26 views

only calculate diagonal of cholesky decomposition

I have a massive matrix $A$ that I can't hold entirely in memory, but it is possible to easily calculate individual entries ($A(i,j)$). I'm only interested in calculating the diagonal entries of the ...
0
votes
0answers
54 views

is 'chasing the bulge' in the implicit QR algorithm exactly the same as reducing a general matrix to hessenberg form?

When performing the implicit QR algorithm, there's a part where you 'chase the bulge' down the diagonal. While it may not necessarily be numerically or computation-time equivalent, is that ...
0
votes
0answers
25 views

How to minimize the peak value of this matrix multiplication?

What range or value of $\theta$ will minimize the peak value of $Y $? $$ Y = \begin{bmatrix} 1+j & 2+j & 3+j & 4+j \\ -4-j & -3-j & ...
0
votes
0answers
140 views

when fixed Point Iteration does not converge?

I want to solve a nonlinear system with the fixed point iteration method. I have initial condition,and the answer is known. By using this method the answer converges very slowly about 1000 iteration ...
0
votes
0answers
53 views

How to solve a divergent linear system using iterative methods?

I have a matrix A which is symmetric and non-diagonal dominant. I tried to use Jacobi/Gauss-Seidel/SOR to solve it but it diverges. Is there any mechanism to condition the matrix for convergence ...
0
votes
0answers
126 views

Row & Column Removal and Rank Reduction

I have a problem involving a n x n square, real matrix $K$ which is initially full rank and is not positive definite. In each iteration of my program, I have to remove a row and the corresponding ...
0
votes
0answers
139 views

Symmetric Tridiagonal QR Algorithm

I have a question regarding QR algorithm. Suppose we are being given a symmetric tridiagonal matrix A (4X4) and perform QR factorization on A: A=QR. Then we define A':=RQ. A' still possesses the ...
0
votes
0answers
42 views

How to write a matrix equation for an underdetermined system

I am having difficulty writing the following equation in matrix form that I can then feed into a computer package to find solutions. The equation I have is: $f_i=g_i(1+\alpha*\exp(2*\pi*i*\lambda))$ ...
0
votes
0answers
55 views

Minimizing an expression with linear constraints

Given a system of under-constrained (i.e. infinite solutions) linear equations (all values will be integers, all coefficients will be 0, 1, or -1), I want to pick values for the variables to minimize ...