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

learn more… | top users | synonyms

0
votes
0answers
15 views

create sparse matrix from diagonal array in matlab

I have the 7 diagonal that come from a 3D finite volume discretization in separate arrays. These 7 arrays have 3D shape and correspond to each elements of the stencil for all points: top, bottom, ...
0
votes
0answers
17 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
53 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
22 views

Diagonal Pivoting Algorithm

Commonly in LU factorization, partial pivoting is used. I know there is another pivoting which is diagonal pivoting. However, on the internet very few resources discussing diagonal pivoting (Only ...
0
votes
0answers
24 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
18 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
26 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
9 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
42 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
24 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
8 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
13 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
21 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
47 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.
0
votes
0answers
32 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
6 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
15 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
29 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
39 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
26 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
40 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
22 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
47 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
46 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
23 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
37 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
24 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
79 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
41 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
43 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
29 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
106 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
96 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
18 views

Complexity of the Product of 2 Orthonormal Matrices

I have two $n \times n$ matrices $A$ and $B$ which are both orthonormal and would like to calculate the product $A^TB$. Is there a way to exploit the orthonormal nature of the matrices to calculate ...
0
votes
0answers
44 views

Counting the number of additions/subtractions for Gauss-Jordan Elimination

We have a matrix of the form $$\Big[\;\;\;n\times n\;\;\;\Big|\;\;\;n\times m\;\;\;\Big].$$ Where the set up is basically solving $m$ linear systems of equations all with the same coefficient ...
0
votes
0answers
40 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
51 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
50 views

Mesh based solution of thin plate spline interpolation

Irregularly spaced elevation data $ \{z(x_i,y_i)\}_{i=1..n}$ can be interpolated using thin plate splines. One way to do this is to use RBFs: link. According to "Scattered Data Interpolation and ...
0
votes
0answers
58 views

Can I realize constraints into an optimization problem like this?

I have a question about adding contraints into optimization problems. I'm reading the book independent component analysis by Hyvärinen and Oja (2001). On page 178, the following formula is given: ...
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
47 views

Very simple question about solving linear systems numerically by using LU decomposition

Say we have the equation $Ax=b$ where we do want to calculate $x$. Why is it useful to make a $LU $ decomposition of $A$ (if possible) ? What are the numerical advantages?
0
votes
0answers
56 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
48 views

Can I detect repeated eigenvalue by inverse iteration?

Suppose all eigenvalues of $A$ are nonnegative. By using inverse iteration $A-\mu I$ for many values of $\mu\ge 0$, I can find eigenvalues of $A$. If $A$ is a $n\times n$ matrix and have different $n$ ...
0
votes
0answers
129 views

Shifted inverse power method in Octave.

EDIT: Ok, I've managed it. It was very stupid bug... I must write $p=L\(P*z0)$ etc.... I'm trying to write a function which returning vector $a$ (vector of eigenvalues of matrix $A=A^T \in ...
0
votes
0answers
31 views

Error bound on matrix vector multiplication

I am multiplying a matrix $A$ with vector $p$. However, the matrix $A$ isn't accurate. Some (a very small fraction) of the element's value is changed from $a_{i,j}$ to {0,$-a_{i,j}$, $2a_{i,j}$}. ...
0
votes
0answers
101 views

Formula for distance travelled?

Given the coordinates of source of a missile, and those of the target both of which are on the surface of the Earth $(z=0)$ , I need to determine the total distance that the missile will need to ...
0
votes
0answers
77 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 ...