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

learn more… | top users | synonyms

0
votes
0answers
3 views

Speeding up Conjugate Gradients iterations for Sparse Matrices?

I've been using Conjugate Gradients to minimize linear systems involving sparse matrices. Although many of my sparse matrices are highly specialized - i.e. for any given row it is easy to know which ...
0
votes
0answers
7 views

Finite difference: Radial symmetry boundary condition in tridiagonal system?

I am putting together an axisymmetric finite difference solver for Poisson's equation over a non-"rectangular" boundary in axisymmetric cylindrical coordinates. I was planning on using the dynamic ...
0
votes
0answers
5 views

Error bounds for solution of system of linear equations when coefficients are uncertain

I have a square system $Ax=b$ and would like to know how much the solution $x$ can change when I change the coefficient matrix $A$. I've stumbled upon the condition number, but this seems to apply ...
1
vote
1answer
17 views

Improving the performance of eigs for a large spd Problem

I have two large (think around $100.000\times 100.000$), sparse, real symmetric and positive definite matrices $A$ and $B$ and I want to find the smallest generalized eigenvalue $$Ax = \lambda_{\min} ...
4
votes
1answer
54 views

What mathematics topics pertain more towards applied mathematics?

I'm entering my second year of undergrad (majoring in mathematics), and I've found that I am really bad at Linear Algebra, but very good at Calculus and Differential Equations. I'm hoping to venture ...
0
votes
1answer
29 views

solve nonlinear system of equation numerically

solve the following system of equations numerically $$2x+2y - e^{xy} = 0$$ $$x^3 + y - xy^3 = 1$$ I'm also asked to solve analytically but I'm pretty sure the closed form solution doesn't exist ...
2
votes
0answers
32 views

Number of Arithmetic Operations in Gaussian-elimination/Gauss-Jordan Hybrid Method for Solving Linear Systems

I am stucked at this problem from the book Numerical Analysis 8-th Edition (Burden) (Exercise 6.1.16) : Consider the following Gaussian-elimination/Gauss-Jordan hybrid method for solving linear ...
3
votes
2answers
91 views

Computing $\operatorname{Tr} \bigl( \bigl( (A+I )^{-1} \bigr)^2\bigr)$

Suppose that $A \in \mathbb{R}^{n \times n}$ is a symmetric positive semi-definite matrix such that $\operatorname{Tr}(A)\le n$. I want a lower bound on the following quantity $$\operatorname{Tr} ...
0
votes
1answer
21 views

Stability of (floating point) computed variance

Homework Question from Accuracy and Stability of Numerical Algorithms, 2nd Edition, by Nicholas J. Higham, page 33: So every time we store an number and do a operation, we introduce an error bounded ...
2
votes
3answers
75 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
35 views

Matrices in Linear Algebra

Let: $ u: \mathbb{R}^2 \rightarrow \mathbb{R}^3$ be defined by: $$ u(x,y)=(x+2y, 2x-y, 2x+ 3y)$$ Give the matrix $M[u]$ in the canonical base of its definition space. This question might seem sort of ...
0
votes
0answers
17 views

What are some possible reasons for a large condition number?

For this question, please assume that I am talking about the condition number with respect to the spectral norm. That is, $\kappa_2(A) = \|A\|_2\|A^{-1}\|_2 = \frac{\sigma_{max}(A)}{\sigma_{min}(A)}$. ...
0
votes
0answers
9 views

Proof of QR Algoirthm Convergence

I am reading Trefthen and Bau and the amount of implicit proof steps are killing me. Can someone explain how the statement of convergence for the "pure" QR Eigenvalue Algorithm (Theorem 28.1) is ...
0
votes
0answers
10 views

how to project optimal parameters on to feasible region

Hi: I'm trying to understand the concept of projection and I created a toy example that might help me to do that. Suppose that I have a non-linear optimization with 3 parameters theta_1, theta_2 and ...
3
votes
3answers
57 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
2answers
331 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 ...
2
votes
1answer
24 views

LU factorization accuracy

I'm doing some experiments with LU factorization (without pivoting). Basically I have a 2x2 matrix and a $b$ vector and I try to solve Ax=b. $A$ looks like: \begin{pmatrix}a&1\\1&1\\ ...
0
votes
0answers
33 views

Parametrization of the $Ax=b, x \geq 0$ domain for Monte-Carlo simulation

I have a linear system, $n=15$, with $6$ constraints. There's no problem finding a single solution or establishing the null space; so I can see the full solution space. But I'm only interested in ...
7
votes
4answers
410 views

Solve quadric equation system

How to solve this analytically(not a numerical solution)? For given real and symmetric matrices $A_1,A_2,A_3,A_4\in\mathbb{R}^{4\times4}$ find $0\neq x\in\mathbb{R}^4$ $$x^TA_1x=0$$ $$x^TA_2x=0$$ ...
1
vote
1answer
36 views

Generate a random neutrally stable matrix

I need to generate random real matrices such that all eigenvalues have real part equal to 0 -- i.e. random neutrally stable matrices. What's the simplest way to do this? Note that I don't care about ...
4
votes
1answer
33 views

LU decomposition for cyclic tridiagonal matrices

It is known that a tridiagonal matrix $$ A = \begin{pmatrix} b_1 & c_1 & 0 & 0 & \dots & 0\\ a_2 & b_2 & c_2 & 0 & \dots & 0\\ 0 & a_3 & b_3 & c_3 ...
0
votes
0answers
10 views

Linear Relationship of two equations

if $0.46a = 120b$ and $2.68a = 60b$ The relationship is linear. what does $0b$ equal in terms of $a$? what does $1b$ equal in terms of $a$? A method to work this out would also be nice, I have ...
1
vote
1answer
13 views

Gauss Seidel Iteration for a specific matrix

We seek to solve $Au= f$ via iteration, where $$ A = \left ( \begin{array}{cc} I & S \\ -S^T & I \end{array} \right ) $$ Where $S$ is an arbitrary square matrix in $R^n$ and $I$ is the ...
1
vote
1answer
40 views

Strange behavior with coordinate transformation of square and quadrilateral

I am trying to map coordinates from a quadrilateral to a square. The coordinates are square: $(500,900)(599,900)(599,999)(500,999)$ quad: $(454,945)(558,951)(598,999)(499,999)$ where the $i^{th}$ ...
1
vote
0answers
35 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 ...
0
votes
0answers
40 views

Most stable algorithm to solve a system of linear equations?

I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to ...
0
votes
1answer
22 views

Notation regarding linearization near equilibrium point of dynamical system

Suppose we have $\frac{dx}{dt} = \dot{x} = f(x)$ with equilibrium point $x_e$ such that $f(x_e) = 0$. Then for the linearized approximation of the differential equation near $x_e$ we hope to use the ...
0
votes
1answer
46 views

Bound on the difference of matrix diagonals

I have two diagonal matrices $\Lambda,\hat{\Lambda}\in\mathbb{R}^{n\times n}$ with non-negative diagonal elements. And I have two matrices $W,\hat{W}\in\mathbb{R}^{m\times n}$, with $m\geq n$, each ...
0
votes
1answer
24 views

Product rule in discrete derivative in finite difference scheme.

Suppose we are on real line and I want to discretize the usual derivative operator. Take a smooth function $u$ and step size $h$. Then I could define $$ \Delta_+u(i) = \frac{u(i+1)-u(i)}{h} $$ as the ...
1
vote
1answer
30 views

How to determine positive or negative definite of a bordered Hessian ?

I want to determine the minimization result I get using Lagrange Multiplier method is a local minimum by determining whether the Bordered Hessian is positive definite or negative definite.(Hopefully ...
-8
votes
0answers
34 views
0
votes
0answers
14 views

What is the source of the error in the Sherman-Morrison formula application?

The Sherman-Morrison formula results in small errors in relation to the standard matrix inverse operation after each application, as shown here. From what I understand, the Sherman-Morrison identity ...
2
votes
1answer
99 views

compute the bisecting normal hyperplane between two $n$-dimensional points.

I have two points $\mathbf{x_1}$ and $\mathbf{x_2}$, where $\mathbf{x_i}=\{x^i_1, x^i_2, \ldots, x^i_n\}$. I need to find a normal hyperplane $P$ that goes through the midpoint of $\mathbf{x_1}$ and ...
1
vote
2answers
40 views

Linear combination of basis function in logarithm space. Is it possible?

I have a function $f(x)$. As theory said that it can represent by linear combination of basis functions such as $$f(x)=\sum_{i=1}^{N}\alpha_ig_i(x)$$ where $\alpha$ is coefficient and $g(.)$ is basis ...
2
votes
0answers
76 views

Best way to solve specific block-tridiagonal linear system (10000x10000 and larger)

To provide more context, this system came from energy balance equation on a mesh with (n,m) nodes in each direction. It's a linear system that looks like this (size of system in blocks n = 4, size of ...
1
vote
2answers
108 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^* ...
1
vote
0answers
15 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
2answers
965 views

Gauss-Seidel method convergence algorithm

From Wikipedia: The convergence properties of the Gauss–Seidel method are dependent on the matrix A. Namely, the procedure is known to converge if either: ...
0
votes
1answer
29 views

Gauß-Newton Example with one variable

$$T=f(t):=2 \alpha + \sqrt{\alpha^2+t^2}$$ To estimate $\alpha$ we got the measured values $T_i$ for $t_i$. Formulate the curve fitting problem and show each step in the Gauss-Newton algorithm. My ...
2
votes
1answer
37 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 ...
1
vote
1answer
57 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
149 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
211 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
633 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
32 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 ...
7
votes
0answers
67 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
33 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
65 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
24 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
363 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, ...