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

learn more… | top users | synonyms

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
79 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
798 views

What is the Moore-Penrose pseudoinverse for scaled linear regression?

The matrix equation for linear regression is: $$ \vec{y} = X\vec{\beta}+\vec{\epsilon} $$ The Least Square Error solution of this forms the normal equations: $$ ({\bf{X}}^T \bf{X}) \vec{\beta}= ...
2
votes
0answers
105 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} ...
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
160 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
63 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
167 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
206 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
161 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
63 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
194 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
26 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
80 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
140 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
184 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
44 views

Analytic Bounds for Eigenvalues of a 2x2 Block Matrix

I am trying to find conditions under which all eigenvalues of M will have nonpositive real part (i.e. M is negative semidefinite, I think). $$M = \begin{bmatrix} A & BE^T\\ CE & D\\ ...
1
vote
0answers
12 views

Numerical algorithm for largest Eigenvalue problem

I am dealing with calculating an eigenvalue problem for differential operator of order 4: $$ \alpha \cdot\Delta^2 u+\Delta u-\Delta(u\cdot u_p(x))=\lambda u $$ where $\alpha\in \mathbb{R}$, $\Delta$ ...
1
vote
0answers
27 views

Computing Cholesky Factorisation by Hand

It is a common exam problem to compute the Cholesky factorisation of a small (typically 4x4) matrix. I know that this can be done by first finding the matrix $U$ in the $LU$-decomposition (e.g. by the ...
1
vote
0answers
25 views

Perturbation of a linear homogeneous equation system

Let $A$ be a $n\times(n+1)$ matrix, full row rank. Let $\tilde A=A+\Delta A$ be a perturbation of $A$, again with full row rank. I am interested what is known about bounds on the angle between the ...
1
vote
0answers
15 views

Non-linear ODE with diagonal matrix

I have a differential equation of this form: $\frac{dX}{dr}(r)$= M(r)X(r)$ + (\sum_{i}X_i) D(r)X(r)$ $X(r)$ is a size n vector. $M(r)$ and $D(r)$ are n x n matrices with $D(r)$ diagonal. They are ...
1
vote
0answers
27 views

Existence of Non-Commutative $4 \times 4$ Matrix Multiplication Algorithm

This paper by a Russian gentleman gives an optimal (?) algorithm for $3$ $\times$ $3$ matrix multiplication. It beats a previously known method by reducing the total number of discrete operations from ...
1
vote
0answers
27 views

Numerical Methods for finding eigenvalues of large matrices.

I'am writing a small research paper on a problem in linear algebra of my choice. I have chose to do the eigenvalue/vector problem. I know that finding eigenvalues gets pretty much impossible if the ...
1
vote
0answers
13 views

for a hermitian matrix, how can I compute the condition number for finding an eigenvalue?

Let $A$ be $m \times m$ hermitian matrix. Let $x$ be a right eigenvector of $A$ with associated eigenvalue $\lambda$. How can I show that the condition number $\kappa $ of computing an eigenvalue is ...
1
vote
0answers
11 views

Solving a system of PDE by fixed point Gauss-seidel iteration method

I have the following system of PDE $$ u-u_0=\operatorname{div}\left(\frac{\nabla u-w}{|\nabla u-w|}\right) \tag 1 $$ $$ \frac{w-\nabla u}{|w-\nabla u|} = \operatorname{div}\left(\frac{\nabla ...
1
vote
0answers
50 views

Given a CRS stored matrix A, provide an algorithm for calculating vector u.

Given an $NxN$ matrix $A$ and vectors $u,v,b$ such that: $$u_i = {\frac1{a_{ii}}}(b_i - \sum_{j=1,j\neq{i}}^n a_{ij}v_i)$$ And considering $A$ is stored using CRS, provide an algorithm (or ...
1
vote
0answers
113 views

GAXPY Operations

Let A ∈$R^2$, x ∈ $R^k$. Find the first column of M = (A − x1I)(A − x2I)...(A − xkI) using a sequence of GAXPY’s operations. GAXPY: General matrix A multiplied by a vector X plus a vector Y. I tried ...
1
vote
0answers
27 views

Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include: All vectors in $S$ All vectors in $T$ All vectors that can be ...
1
vote
0answers
37 views

Computational methods to minimizing the norm of a matrix monomial.

Linear optimization solves the problem $$\min_{\bf x}\{\|{\bf Ax - b}\|_2^2\}$$ Edit: Some clarification Doing the derivation of the optimum, first expand the norm: $$\|{\bf Ax - b}\|_2^2 = ({\bf ...
1
vote
0answers
39 views

How can I write $\prod\limits_{i = 0}^n {\left( {x - {x_i}} \right)} $ in terms of a polynomial as $\sum\limits_{i = 1}^n {{a_i}{x^n}} $?

How can I write $\prod\limits_{i = 0}^n {\left( {x - {x_i}} \right)} $ in terms of a polynomial as $\sum\limits_{i = 1}^n {{a_i}{x^n}} $? In the other words, is there a way to write $a_i$ in terms of ...
1
vote
0answers
22 views

Conditional expectation of a set of Gaussian variables

I was wondering if there is an efficient way to compute the conditional expectation of every element in a Gaussian random vector ? Specifically: For a pair of Gaussian random variables $[x,y]$, the ...
1
vote
0answers
33 views

How to apply Runge-Kutta to an implicit scheme?

I see there are some differences in the solution as I increase the resolution of my grid. I'm using Operator Splitting to solve Diffusion Reaction equation \begin{equation} \frac{\partial ...
1
vote
0answers
18 views

Relationship between QR and LU factorization

Both algorithm return very similar results in terms of having a upper/right triangular matrix as one of the factors. What is the relationship between Q and L, and between R and U? What is the ...
1
vote
0answers
25 views

How can I solve this specific set of equations?

Here are the equations: $$\sum_{k = 1}^n i_k + Y_n u_n = J \quad \quad (1)$$ $$i_1 + Y(u_1 - u_2) = J \quad \quad (2)$$ $$i_k - Y(u_{k - 1} -2u_{k} + u_{k + 1}) = 0, \quad \quad k = 2, ..., n - 2 ...
1
vote
0answers
83 views

Numerically stable SVD

In this question regarding SVD, it is explained why eigen decomposition of $ A^tA $ is not numerically stable compared to "direct SVD algorithms". Since the former is the algorithm I'm most familiar ...
1
vote
0answers
41 views

Numerically finding eigenvalues of a Volterra operator of first kind

I'm looking for a solution to the following problem - $\int_{-\infty}^{\infty} K(x-y) f(y) = \lambda f(x)$ Consider $K(x-y) = \left\{ \begin{array}{lr} e^{-(x-y)} & : x > y \\ 0 & : x ...
1
vote
0answers
42 views

Ideas for expressing the inverse of matrix quadratic form $CAC^T$

I want to find an expression for the inverse of the matrix system $Z=CAC^T$, where $A \in \mathbb{C}^{n \times n}$ is block diagonal with dense blocks, and $C \in \{-1,0,1\}$ with dimension $m \times ...
1
vote
0answers
99 views

Eigenvalues after Givens-Rotation

Im just validating my own Code of a Givens-Rotation in Matlab. Therefore i let matlab compute the Eigenvalues after each Givens-Rotation. I am wondering why the Eigenvalues computed by matlab are ...
1
vote
0answers
54 views

Simplifying the Generalized Eigenvalue Problem

Let $\Sigma_1$, $\Sigma_2$ be symmetric positive-definite real $n\times n$ matrices. We want to solve the generalized eigenvalue problem $$ \Sigma_1V=\Lambda\Sigma_2V, $$ where $\Lambda$ is the ...
1
vote
0answers
64 views

complex rank-one update

I'm trying to find the eigendecomposition of a rank-one update to a complex matrix $D + uv^T$. The matrix $D$ is diagonal, but not the identity. It has unique imaginary entries along the diagonal. ...
1
vote
0answers
49 views

Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay the same

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, ...
1
vote
0answers
24 views

Overdetermined system with discrete data.

The setup I have a set of experimental data (subscript 1) which calculates two variables $u_1(x,y,z)$ $v_1(x,y,z)$ I can calculate the three spatial gradients for my two variables ($u_1$ and ...
1
vote
0answers
35 views

QR Algorithm fails under certain conditions

First of all, i have to admit that i am really knew to this numeric stuff. I have to detect two complex Eigenvalues of a Matrix and therefor i implemented some easy QR-Algorithm with MatLab. I am ...
1
vote
0answers
41 views

$Az + B\overline{z}$ as a linear operator

Given two matrices $A,B \in \mathbb{C}^{n\times n}$ with fixed $n\in\mathbb{N}^+$, let us consider the operator $$ L:\mathbb{C}^n \to \mathbb{C}^n,\\ L(z) = Az + B\overline{z}. $$ This operator is not ...
1
vote
0answers
97 views

Row degeneracy in systems of linear equations

I am trying to understand the concept of row degeneracy in a system of linear equations, but having trouble understanding this problem. \begin{align} x+2y+z &= 2 \tag{1} \\ 2x+y+3z &=5 ...
1
vote
0answers
13 views

Enforcing additional constraints in linear equation

In a finite element context, I come up with a sparse "stiffness matrix" $A$ and a corresponding RHS $b$. The goal is now to solve $$Au = b$$ Where $u$ is a coefficient vector of the solution. Now I ...