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

learn more… | top users | synonyms

3
votes
1answer
54 views

Necessary and Sufficient conditions for convergence of matrix iterations

I need some help figuring out how to go about the iteration part of the problem...I don't really know where to start. If someone can please help take me through it that would be greatly appreciated. ...
3
votes
1answer
119 views

A Beautiful Determinant!

Find the determinant of the following matrix in the terms of $a_1,a_2,\cdots,a_n$ explicitly, $$ \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_n\\ a_2 & a_3 & a_4 & \cdots ...
0
votes
0answers
37 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
23 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
40 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
13 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
18 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
23 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
16 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
51 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
51 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
36 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
47 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
26 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
80 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
53 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
50 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
106 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
52 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
46 views

Find nullspace from one removed column

I have a large, sparse, square matrix $B$ that is full rank, and am going to remove one column from it to get a new matrix $B_{red}$. I also have a matrix $S$ of candidate columns, one of which needs ...
0
votes
0answers
44 views

code to factorize block toeplitz matrix fast and stable

My goal is to factorize (LU or QR) a symmetric, semi-positive block Toeplitz matrix as quickly and as stably as possible. A classic fast algorithm, for example, is the Levinson algo, but it is rather ...
0
votes
0answers
117 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
23 views

Calculating a 3d vector based on two functions based on time

I have an object who's position is defined by a 3d vector, startposition. I want to translate this object towards another position, endposition. At the same time, I also want to translate this ...
0
votes
0answers
33 views

How to generate random matrices when it's singular values are given?

Consider matrix S as nxn diagonal matrix with singular values populated across the diagonals in non-increasing order. I want to know how to create random matrix A whose singular values with be the ...
0
votes
0answers
114 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
41 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
53 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 ...
0
votes
0answers
47 views

Is there any risk to transform to $(B^{T} \otimes A)\operatorname{vec}(X)=\operatorname{vec}(C) $ for solving $AXB=C$ for X

To solve the equation $AXB=C$ for X, we can use the property of vec operator and kronecker product to transform to $(B^{T}\otimes A)\operatorname{vec}(X)=\operatorname{vec}(C)$, where ...
0
votes
0answers
73 views

Shear decomposition

Is there an algorithm for decomposing a square matrix (or a similar matrix to it) in to shear and diagonal matrices? All the usual decompositions (Schur, SVD, QR, LU, etc.) don't seem to help. ...
0
votes
0answers
83 views

Can antiunitary symmetry be used to calculate determinant of a matrix

Suppose I have some $N \times N$ complex matrix $A$, that commutes with some antiunitary operator $U$ that satisfies $U^2 =-1$. It can be shown that $\det(A)\ge 0$ , because for every eigenvector ...
0
votes
0answers
44 views

Derivative of $H$ with respect to $W$

I am trying to solve a generalized linear squares model with the following form: $\hat{Y}= X(X'\Omega^{-1}WX)^{-1}X'\Omega^{-1}WY $ $ H= X(X'\Omega^{-1}WX)^{-1}X'\Omega^{-1}W $ $ \Omega$ is the ...
0
votes
0answers
124 views

Divide and conquer possible on linear equation systems?

Suppose a 4-connected regular grid $$\mathcal{G}=(\mathcal{E},\mathcal{V}),$$ where $\mathcal{E}$ and $\mathcal{V}$ denote the set of edges and vertices of that grid, respectively. Given this ...
0
votes
0answers
73 views

relative error relation

Let $x$ be a non-null quantity. Let $\hat{x}$ be its approximation. I am trying to find the relation between: $\frac{\left | x-\hat{x} \right |}{\left | x \right |}$ and $ \frac{\left | x-\hat{x} ...
0
votes
0answers
41 views

Issues with the value of the last element in Cholesky decomposition

I am trying to calculate the Cholesky decomposition of a precision matrix. I was expecting a Lower triangular matrix $L$ where $L_{ii}>0$ for all $i$. However, the last element in the diagonal is ...
0
votes
0answers
277 views

Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $F(x)$ $F(x) = \sum_{i=1}^{M}||x_{i+1} - x_i - K(\frac{x_{i+1} + x_i}{2})||^2 + ||x_1-c_1||^2 + ||x_N-c_2||^2$ , where $x$ is a vector of $N$ scalars, $c$ are ...
0
votes
0answers
233 views

Householder Transformation

Let $\mathbf{a}\in\mathbb{R}^{n}$ be a non-zero vector. Develop a numerically stable procedure to compute a Householder transformation P such that $$P\mathbf{a}=\left(\begin{array}{c} ...
0
votes
0answers
64 views

Can this be expressed as an LLSQ problem? $||Ax - b|| = c$

I'm trying to minimize the following: $||Ax - b|| - c$ where: $A$ : $K \times M$ matrix $x$ : $M \times N$ unknowns ($M$ $N$-dimensional vectors) $b$ : $K$ $N$-dimensional vectors $c$ : $K$ ...
0
votes
0answers
109 views

Efficient principal pivots

Background I'm working on a numerical linear algebra package in C#. I'm trying to implement a variety of "principal pivoting" methods to solve optimization problems (specifically linear ...
0
votes
0answers
57 views

Diagonalising a huge matrix of symbolic objects

I have to diagonalise this HUGE $9\times 9$ matrix with symbolic entries which are made up of three independent variables. Can you please give me a reference as to how to do such a thing ...
0
votes
0answers
93 views

Does a single Gauss-Seidel iteration lead to unique coordinates?

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$, and $x,y\in\mathbb{R}^{n\times 2}$ are ...
0
votes
0answers
45 views

Lower Rank Matrix

Given I have a matrix A of rank 3. I want to create a matrix of Rank 2 which is closest to A in the $ {l}_{2} $ / Frobenius norm. Let's call this matrix F. Is easy to achieve by the SVD, namely, if $ ...
0
votes
0answers
141 views

Singular value decomposition, possible property

Suppose a singular value decomposition on matrix $P\in\mathbb{R}^{n\times m}$ is given, $P=U\Sigma V^T$ with $U=[u_1,\dots, u_n]\in\mathbb{R}^{n\times n}$, $u\in\mathbb{R}^{n}$, containing the ...
0
votes
0answers
165 views

Estimating a solution with the Jacobi Method for solving Ax = b

I'm trying to understand how the Jacobi method works and would appreciate a walk-through of the method with a very very simple example. In particular, I don't fully understand how one goes from the ...