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

learn more… | top users | synonyms

1
vote
1answer
21 views

Choose $\rho$ such that $\rho$-norm minimizes the matrix condition number

I'm solving questions from am exam that I failed miserably, so I would love it if someone can take a look at my proof and make sure I'm not making any gross mistakes. Question Let $A$ a symmetric ...
0
votes
1answer
27 views

Is this a circulant matrix?

It's symmetric, but I'm not sure whether it is circulant. In a question that I had asked on MSE a couple of weeks ago, several commenters had said that this is a circulant matrix, and to study the ...
1
vote
1answer
33 views

How to numerically solve the Poisson equation given Neumann boundary conditions?

I want to solve the Poisson equation on a 2D domain given Neumann-type boundary conditions: The PDE: \begin{equation} \nabla^2 \; u(r,\theta) \;=\; f(r,\theta) \end{equation} The boundary ...
0
votes
0answers
126 views

Generalized SVD and weighted SVD

I've the following question: How should I select the $A$,$B$ matrices in the generalized singular value decomposition (GSVD) such that it solves the weighted version of the generalized singular value ...
1
vote
1answer
206 views

Simultaneous Eigenvalue Problem

I have what I think is a simultaneous eigenvalue problem in three parameters: $$\alpha A_1x + \beta B_1x + \gamma C_1x + D_1x = 0$$ $$\alpha A_2x + \beta B_2x + \gamma C_2x + D_2x = 0$$ $$\alpha A_3x ...
1
vote
1answer
632 views

How to find the Householder transformation?

Assume $x=(1,0,4,6,3,4)^T$. Find a Householder transformation and a positive number $\alpha$ such that $Hx=(1,\alpha,4,6,0,0)^T$. I'm sorry that I don't know how to start with this problem. A ...
0
votes
1answer
27 views

Automatic way to have a good initial guess for the iterative methods ( newton method) and for high dimensional nonlinear problems

I am solving a variety class of nonlinear systems where I need to reduce in optimal manner the number of iterations of either the newton or modified newton method. For this end I am trying to figure ...
6
votes
0answers
59 views

How to solve linear system of form $(A \otimes B + C^{T}C)x = b$ when $A \otimes B$ is too large to compute?

For the given linear system: $$(A \otimes B + C^{T}C)x = b$$ where $\otimes$ is the Kronecker product, $A$ and $B$ are dense and symmetric positive-definite, and $C^{T}C$ is a sparse symmetric block ...
0
votes
0answers
29 views

How to calculate $det(X^T X)$ efficiently, update one column of X each time

$X_{1} = (A, b)$, where $X_{1}$ is a $n\times p$ matrix, $A$ is a $n\times (p-1)$ and $b$ is $n\times1$. First calculate $\det(X_{1}^T X_{1})$, then update $b$ with $c$, st. $X_{2} = (A, c)$ and ...
1
vote
1answer
64 views

Most efficient way to find distinct complementary subspaces over a finite field

Let $V$ be a $n$-dimensional vector space over $\mathbb{F}_p$ and let $W$ be a $k$-dimensional subspace. What's the most efficient way to algorithmically write down a basis for each distinct subspace ...
0
votes
1answer
21 views

Can adding one column to a matrix increase its rank by more than one

Knowing the answer to this question would help me answer the following question: $A$ is an $m\times n$ matrix with $m>n$, and let $A=\hat{Q}\hat{R}$ be a reduced QR factorization. Suppose ...
1
vote
0answers
358 views

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

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

Space spanned by matrices

I have a set of 5 by 5 matrices, M1,M2,...,M19 ,M20. I want to try to find a basis from this set and also to find relationships between these matrices. This is how I think I should approach the ...
0
votes
2answers
28 views

Rewrite matrix equation as a quadratic programming problem

Given real-matrix $X_{n\times p}$ how can the problem of minimizing $Tr(X^TA_{n\times n}X)$ under the constraint $Tr(X^TC)=\phi$ be posed as a standard convex quadratic program given by the form: ...
0
votes
0answers
22 views

Efficient method to compute grand sum of a Vandermonde matrix?

Is there a computationally efficient method to calculate the sum of all elements (grand sum) of a Vandermonde matrix? Each row can be quickly calculated using the formula for a geometric progression. ...
2
votes
0answers
50 views

Fastest way to find linearly independent columns of a matrix

Given a rectangular matrix $X$ of size $n\times m$ with $m>n$, what is the fastest way to find the linearly independent coloums. Robust methods like SVD or RRQR decompostion have complexity of ...
0
votes
0answers
14 views

Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

I have the following quadratic form I need to evaluate: $x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors. Now assume that I am given for free both $A^{-1}$ ...
2
votes
2answers
36 views

Differential equation for finding closest point on surface.

Inspired by this question I got to think about a more general case. Say I have any discretized surface and want to find closest point from each point outside of surface to the surface. Say that I can ...
1
vote
0answers
25 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
3answers
49 views

Symmetry Of Differentiation Matrix

I have a problem computing numerically the eigenvalues of Laplace-Beltrami operator. I use meshfree Radial Basis Functions (RBF) approach to construct differentiation matrix $D$. Testing my code on ...
0
votes
1answer
48 views

The MU-puzzle from GEB

The MUI system only uses the three letters M,U,and I to make strings. The system has four rules that allow you to make new strings out of existing strings by manipulating them. Rules 1 and 2 lengthen ...
1
vote
0answers
9 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 ...
0
votes
1answer
92 views

Practical examples/implementation details for Gauss-Seidel method

I'm having a presentation on Gauss-Seidel iterative method, and although it isn't mandatory , I would like to have some practical examples for this method (a system of linear equations with n>=1000, ...
1
vote
2answers
33 views

How to solve the system of equations $\{10^{-4}x_1+x_2=1, x_1+x_2=2\}$ using finite precision arithmetic with three significant figures?

Consider the following two equations: $10^{-4}x_1+x_2=1$ $x_1+x_2=2$ Solve using Gaussian Elimination using finite precision arithmetic with three significant figures. I'm a little ...
1
vote
1answer
28 views

Error bound of midpoint rules with unbounded second derivative

It is well known that error bound of midpoint rule for function $f[a,b]$ is given by $$ E\leq K\frac{(b-a)^3}{24 n^2} $$ where $|f(x)''\leq K|$ and $n$ is the number of time steps. if second ...
0
votes
0answers
16 views

Approximation of Mahalanobis distance

If $A$ is a symmetric positive definite $n\times n$ matrix then the square Mahalanobis norm of a vector $v\in \mathbb{R}^n$ is given by $$\lVert v \rVert_A^2=v^t A^{-1} v.$$ Now I have a situation ...
0
votes
0answers
13 views

Proof that Householder Triangularization for QR is backward stable

How do you prove that QR factorization via Householder Triangularization is backward stable? Theorem 16.1 (From Trefethen and Bau): Let the $QR$ factorization of a matrix $A$ be computed by ...
1
vote
0answers
23 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 ...
0
votes
0answers
22 views

Linear algebra <perhaps an application of Gordan' Theorem>

Question. Let $a_1,...a_n\in\{0,1,-1\}^m$ and $\sum a_i=(1,...,1)$. Is there a permutation $\tau$ of $\{1,...,n\}$ Such that for each $k\in \{1,...,n\}$ the vector $\sum_{i=1}^k a_{\tau (i)}$ has ...
1
vote
0answers
31 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
22 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 ...
2
votes
0answers
16 views

Reference request for finite difference method

I am trying to use finite difference method to solve the minimizing problem $$ J[u]=\min_{u\in BV(Q)}\{\|u-f\|_{L^1(Q)}+|u|_{BV(Q)}\} $$ where $Q=(0,1)\times (0,1)$ is a uint square and ...
1
vote
1answer
30 views

What happens if the power method is applied with a starting vector $q=c_2 v_2+…+c_n v_n$ in the presence of roundoff errors?

Supose $\{v_1,...,v_n\}$ is an eigenvector basis and $|\lambda_1|>|\lambda_2|>\ldots >|\lambda_n|>0$, so, my question is, if our starting vector $q \in span\{v_2,\ldots,v_n\}$ and in the ...
4
votes
1answer
131 views

QR decomposition help

What do Q and R stand for? Why must the diagonal entries of R be positive instead of just nonzero?
1
vote
1answer
37 views

What are some Applications of Hermitian Positive Definite matrices?

I am learning about Hermitian positive definite matrices and the way that they can be decomposed with Cholesky decomposition. I have learned that these matrices deserve special attention for how often ...
3
votes
1answer
496 views

Effects of elementary row operation on condition number

How does any elementary row operation on a matrix affect the condition number? Can an ill conditioned matrix be improved by just some elementary row operations? Can I improve the accuracy ...
0
votes
1answer
38 views

Iterative method to compute only the positive eigenvalue's and corresponding eignevectors of a very large matrix?

I have a very large dense matrix (~10000 X ~10000) which is not full rank . I want to compute only the positive eigenvalues and corresponding eigenvectors instead of computing all of them. I have ...
0
votes
1answer
29 views

How to link the eigenvalues to the components from PCA

I have a difference matrix from daily changes which I use to construct a covariance matrix. On this covariance matrix I use the power method to get the eigenvalues. The power method yields exactly the ...
0
votes
0answers
18 views

Is my QZ-Step as postulated in the paper?

I am working with the paper An algorithm for generalized matrix eigenvalue problems from C.B. Moler and G. W. Stewart (paper available here: ...
1
vote
0answers
26 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
24 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 ...
2
votes
1answer
35 views

Solving a system of polynomials in $N$ variables

Suppose I am given some non-negative constants $(C_p)_{p=1, ..., l}$ and I would like to find an integer $N$ and vector $v \in R^N$ such that $$ \sum_{i=1}^N (v_i)^p = C_p $$ for $p=1, ..., l$. Can ...
1
vote
0answers
34 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 ...
2
votes
4answers
63 views

Inverse Chebyshev Recurrence

The Chebyshev polynomials (of the first kind) are a sequence of polynomials defined recursively by $$ \begin{cases} T_{0}(x) = 1 \\ T_{1}(x) = x \\ T_{n}(x) = 2xT_{n-1}(x) - T_{n-2}(x) \end{cases} $$ ...
1
vote
0answers
36 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
27 views

Solving a matrix equation using numerical optimization

To my knowledge, if $A \in \mathbf{S}^n_{++}$, then given any $b \in \mathbb{R}^n$, the system of linear equations $Ax = b$ has a unique solution $x^* \in \mathbb{R}^n$. Moreover, the solution $x^* ...
0
votes
1answer
30 views

Use the Forward Difference method to approximate the solution to the following PDE?

Use the Forward Difference method to approximate the solution to the following PDE: $$ u^3\frac{\partial u}{\partial t}-x^2u\frac{\partial^2u}{\partial x^2}=2x^8t^7+6x^6t^5+4x^4t^3 $$ for $0\le ...
0
votes
0answers
14 views

QZ-Algorithm: how to simultaneously generate the upper triangular form

I need to calculate the Eigenvalues of a generalized Eigenvalue Problem. To achieve this, i wanted to use the QZ-Algorithm, which avoids calculating the inverse of a Matrix. This quite useful, because ...
1
vote
0answers
52 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. ...
0
votes
0answers
34 views

Givens-Rotation from the right

i need to get a Givens-Rotation, which zeros a matrix entry when multiplied from the right side. I did already look at this topic givens rotation from right side but i could not really understand the ...