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

learn more… | top users | synonyms

3
votes
1answer
60 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
135 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 ...
3
votes
1answer
125 views

How to solve this system of 3 equations with 3 variables?

I stumbled upon this system with constants $a_{i,j}>0$ that I want to solve for $x,y,z \in\mathbb{R}$: \begin{align} a_{2,1}y+a_{3,1}z=& x(y+z) \\ a_{1,2}x+a_{3,2}z=& y(x+z) \\ ...
3
votes
1answer
88 views

Understanding higher order SVD

Can someone explain the singular value decomposition of a tensor (maybe a 3 dimensional matrix) with an example? It is intuitively difficult to the get the meaning from just the formulas. On a ...
3
votes
1answer
143 views

Computational cost, power method and page rank

When solving the PageRank problem for $n$ web pages, it is necessary to find a solution of the eigenvector equation $$(fM)*p = p,$$ where $$fM = dM + (1 - d)Z$$ $$Z =\frac{1}{n}*ee^T$$ $$e =[1, 1, ...
3
votes
1answer
226 views

How to Store a Banded Matrix by Diagonal

I'm taking a graduate level independent study course this semester in Matrix Computations. I'm not getting much support from the professor, so am turning to the excellent StackExchange community for ...
2
votes
1answer
38 views

Eigenvectors of transition matrices in PageRank algorithm

In my probability course, we were discussing applications of Markov Chains to computer science -- in particular, how the PageRank algorithm goes about finding stationary distributions, and thus, ranks ...
2
votes
1answer
69 views

Least squares problem with orthonormality constraints

Given $y_1,\ldots,y_n\in \mathbb{R}$,$w\in \mathbb{R}^d$, and $x_1,\ldots x_n\in \mathbb{R}^D$, how do we solve the following optimization problem \begin{align} \min_A \sum_{i=1}^n (y_i-w^TA^Tx_i)^2\\ ...
2
votes
1answer
66 views

fast multiplication for a matrix and its transpose.

I know Strassen and other methods can achieve better than $O(n^3)$ for general square matrix multiplication. I am curious of the spacial case where the multiplication is between a $n*m$ matrix $A$ ...
2
votes
1answer
112 views

SOR and Gauss-Seidel Method - Confusion

Can anyone explain to me the SOR Method for finding the root(s) of a function? Its supposedly very similar to the Gauss-Seidel method. The Gauss-Seidel method, from my understanding, is similar to ...
2
votes
1answer
200 views

1D Schrodinger/Laplace equation via finite differences: incompatible eigenvalues

I need to solve a variant of the 1D Schrodinger's equation equation using finite differences, so I decided to play a little bit with the real-space representation of some operators. Using the ...
0
votes
0answers
41 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
68 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
68 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
25 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
60 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
21 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
57 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
11 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
27 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
17 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
18 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
55 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
57 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
56 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
51 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
152 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
67 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
27 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
146 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
56 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
150 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
43 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
59 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
48 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
82 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
99 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
144 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
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
327 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
256 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
115 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
94 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
146 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
180 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 ...