Numerical algorithms for problems in analysis and algebra, scientific computation

**0**

votes

**0**answers

123 views

### Can we separate Toeplitz matrices for negative and positive eigenvalues?

Consider a Toeplitz matrix T which has both positive and negative eigenvalues. Can we prove that there exist two Toeplitz matrix T1 and T2 such that T1+T2=T and T1 has only one positive Eigenvalues ...

**2**

votes

**0**answers

238 views

### How to apply Lagrange Multipliers to BCs of Time Dependent problems using finite elements?

I am trying to implement a finite element scheme using the method of lines (finite difference in time and finite element in space) and enforcing boundary conditions using Lagrange Multipliers. This ...

**7**

votes

**2**answers

999 views

### Finding the smallest eigenvalues of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $M$. $M$ is a Laplacian matrix, and it has the following structure: ...

**8**

votes

**4**answers

642 views

### What is the theoretical interest of finding closed-form sols. of infinite series?

Hi,
I was reading this when I came across Gourevitch's conjecture.
My understanding is that solutions to these series are of practical interest. If one encounters such a series, being able to solve ...

**1**

vote

**2**answers

189 views

### Triangular grid with 4 edges per vertex

I am trying to create a triangular grid/mesh for a rectangular domain in $\mathbb{R}^2$ with the property that each vertex is shared by (at most) four edges. Is this possible to accomplish?

**1**

vote

**1**answer

176 views

### Distributions induced by (weighted) random walks on the integer lattice

Consider an integer lattice $\mathbb{Z}^2$ where grid points are separated by a distance $h$. Loosely speaking, a random walk of length $k$ is a sequence of lattice points $(x_1,\cdots,x_k)$ ...

**7**

votes

**2**answers

828 views

### Mathematical computer desk [closed]

D. Gibb, from the Mathematical Laboratory, University of Edinburgh,
describes a Computer Desk in his book A course in interpolation and numerical integration for the
mathematical laboratory, G. Bell ...

**3**

votes

**1**answer

247 views

### Stability of Levinson-Durbin method for Toeplitz system solutions ?

How stable is Levinson-Durbin method for solution of systems of linear equations ?
I mean if condition number of matrix is $k$, does intermidiate steps involve matrixes
with higher condition number ...

**12**

votes

**0**answers

272 views

### Descartes rule of signs for a noncommutative polynomial in matrix variables

Recently, while studying certain notions of "averaging" a set of input matrices, I obtained a nonlinear polynomial in matrix variables. A simple example is
\begin{equation*}
\mathcal{G}(X) := X^n - ...

**3**

votes

**2**answers

362 views

### battleship permutation

Consider the following one-dimensional version of the game battleships. There is a battleship somewhere on $\mathbb N$, i.e., a interval $N,\ldots,N+k$. Your task is to find whether this battleship ...

**2**

votes

**2**answers

2k views

### Numerical Computation of arcsin and arctan for real numbers [closed]

I'm coding some numerical methods and I do not know what the correct analysis would be for choosing the implementation for $arcsin$ and $arctan$ for real numbers. Here's what I know:
Both functions ...

**0**

votes

**1**answer

136 views

### eigenvector update formula

Suppose that $B$ is a Hermitian matrix with one known eigenpair $(\lambda,v)$. (assume its the smallest or largest pair, if you like). Form the rank one update $B+\rho bb^{T}$.
Now I'm interested in ...

**3**

votes

**2**answers

218 views

### Convergence rate of an iterative process

I have the following iterative process
$$a_n=a_{n-1}(1-\phi(a_{n-1})),\quad 0< a_0<1,$$
where $\phi(x)$ is a continuous increasing function, $\phi(0)=0$, and if $x\in(0,1)$ then $0< ...

**4**

votes

**2**answers

278 views

### Evaluating a limit similar to the Euler constant

In the course of studying a certain complex-valued functional equation, I have had a need to evaluate the following limit:
$$\gamma_\mathcal{T}=\lim_{n\to\infty}\left(-\frac{i}{2}\sum_{k=1}^n ...

**2**

votes

**3**answers

210 views

### 'Condition number' for Rayleigh-Ritz quotient

Suppose that $A$ is a Hermitian matrix and that $u,v$ are two vectors. Is there some known function $\kappa(A)$ so that $||u-v|| \leq \kappa(A) |\frac{u^{\*}Au}{u^{\*}u}-\frac{v^{\*}Av}{v^{\*}v}|$?
...

**0**

votes

**1**answer

650 views

### Frequency calculation using fourier transform [closed]

How to calculate the frequency of an audio file using Fourier Transform

**5**

votes

**1**answer

399 views

### Rational approximation to a set of reals

Are there any well known algorithms for finding good rational approximations to sets of real numbers?
Given just two real numbers, I can use continued fractions to find a rational approximation to ...

**0**

votes

**2**answers

109 views

### solving non linear equations

When solving non-linear equations via Newton's method, load increments are often used to improve convergence. In mechanics for example, if the final load in 90N, one could choose 3 load steps of 30N ...

**2**

votes

**0**answers

483 views

### Problem using finite difference to solve a initial value problem

Hallo, I tried to use 'finite difference' method to solve a Initial Value Problem(IVP). For the two boundaries I used periodical condtion and for the differential operators I used 4th degree center ...

**7**

votes

**6**answers

759 views

### Applications of group theory in numerical analysis?

Are applications of group theory known to exist in numerical analysis?
One particular aspect I am curious about is whether matrix groups have been successfully used to derive algorithms.
Also, are ...

**28**

votes

**11**answers

5k views

### “Must read” papers in numerical analysis

In 1993, Prof. L.N. Trefethen published a NA-net posting with a list of thirteen paper he used for teaching the seminar Classic Papers in Numerical Analysis.
In Trefethen's words, ... this course ...

**0**

votes

**1**answer

162 views

### Ease of calculation of norm

I have SPD matrix A and two vectors z and b.
Is there exist a norm where I can calculate $||A^{1/2}b-z||$ without having to calculate $A^{1/2}b$ explicitly ?

**0**

votes

**2**answers

245 views

### Convergence of Fourier series for $C^p$ functions

Let $f \in C^p[0,2\pi]$ and periodic. Denote $\omega_p$ as the moduli of continuous of $f^{(p)}$. Then
$
|f - S_Nf| \le K \frac{\log{N}}{N^p}\omega_p(2\pi/N),
$
where $S_N$ is the Fourier partial sum ...

**5**

votes

**0**answers

125 views

### reference for perturbation of projection result

Let $A$ and $B$ have the same rank and dimensions. If $P_A$ denotes the projection onto the range space of $A$, then
$$
\|P_A - P_B\|_2 \leq \|A - B\| \cdot \min (\|A^\dagger\|_2, \|B^\dagger\|_2).
$$
...

**1**

vote

**1**answer

248 views

### Stieltjes convolution with white noise

I'm looking for a reference that would discuss a Stieltjes convolution between a wiener process and a function of bounded variation. Additionally, I had a question about this sort of convolution.
Is ...

**2**

votes

**4**answers

288 views

### Avoiding overfitting by averaging polynomials fit to part of the data?

I was thinking about the problem of overfitting data. Suppose you have a hundred data points sampled from an unknown function (call this the training set). You could try fitting a ...

**4**

votes

**0**answers

271 views

### Extreme eigenvalues of real symmetric matrix with main diagonal variance twice non-diagonal

Main question
Suppose there exists a random real symmetric $N \times N$ matrix $A$ with the main diagonal elements distributed according to $\mathcal N(\mu = 0, \sigma^2 = 4N)$, while all ...

**0**

votes

**0**answers

119 views

### Finding peaks and determining noise

Hello ,
Im having one matrix which is product of two FFT transforms of one fits image ( astronomical image ). In that matrix you could find 3 peaks. One largest in center, and two around central ...

**3**

votes

**2**answers

2k views

### Computational complexity of calculating the nth root of a real number

Several sources state that the computational or time complexity of square rooting is the same as that of multiplication (or division). See for example:
Jean-Michel Muller, "Elementary Functions: ...

**0**

votes

**1**answer

219 views

### Moore-Penrose bound question

Suppose that we are given an equation $Ax=b$. The minimum least-squares solution is of course $x_{m}=A^{\dagger}b$. What I want to know is whether there are known bounds on $||x-x_{m}||$. In the ...

**3**

votes

**2**answers

252 views

### an equation in fractions

I have an equation of the form $\sum_{i=1}^{m}{\frac{1}{a_{i}-x}}=\sum_{j=1}^{n}{\frac{1}{b_{j}-x}}$ and would like to express $x$ as a an approximate explicit function of the $a_{i},b_{j},m,n$. Have ...

**4**

votes

**2**answers

277 views

### Convolutive noise removal

I have the time domain signal
$$
u_o(t) = u(t)e^{-t/\tau}\eta(t) + \sigma(t)
$$
where $\tau$ is known, $\eta$ is non-Gaussian noise, and $\sigma$ is Gaussian noise. The distribution of $\eta(t)$ is ...

**2**

votes

**2**answers

109 views

**2**

votes

**2**answers

311 views

### My overdetermined linear system gives both bad and good estimates. Why ?

Hello to everyone.
What the question means is that different ways of
expressing the same relation between the data and unknown variables produce
really weird fit results:
The problem:
I have the ...

**2**

votes

**2**answers

375 views

### A sum of eigenvalues

Let $X$ be an $n\times n$ symmetric matrix. Suppose $\lambda_1(X)\geq \lambda_2(X) \geq \cdots \geq \lambda_n(X)$ are eigenvalues of $X$. Let $r$ be any integer with $1\leq r\leq n$. It is well-known ...

**3**

votes

**1**answer

107 views

### exact simulation of a large sample histogram

Say I want to create a histogram of $N$ samples from some simple compactly supported distribution on $\mathbb{R}$, where $N$ is very large, say $N = 10^{30}$. The histogram has $K$ disjoint bins, ...

**3**

votes

**2**answers

748 views

### How to solve a fifth degree polynomIal

Charles Hermite have created a method using elliptic fonctions, to solve fifth degree polynomial, to get around the theory of gallois. Can someone explan me it and give a simple exemple ?
Tank you

**4**

votes

**1**answer

1k views

### Weyl inequalities for largest eigenvalue of matrix sum

The $k^{\rm th}$ largest eigenvalue (arranged in decreasing order) of the sum of two $N \times N$ Hermitian (real symmetric) matrices $\bf{A}$ and $\bf{B}$ can be stated using the Weyl inequalities as
...

**5**

votes

**3**answers

376 views

### Error in Polynomial Root Finding Algorithm with Synthetic Division

I have written a program which finds the roots of polynomial using Newton's Method. After finding the first root to within a tolerance (note that this also finds complex roots), I use synthetic ...

**5**

votes

**3**answers

1k views

### Eigenvalues of non-symmetric matrix and its transpose

What more can be said about the eigenvalues (especially the spectrum) of the $N \times N$ matrix ${\bf M} = {\bf A} + {\bf A}^T$ in terms of $\bf A$ if $\bf A$ is not symmetric and its eigenvalues are ...

**1**

vote

**0**answers

292 views

### Monte Carlo sampling high dimensions with the halton sequence?

Referring to the Halton Sequence, Swiler et al 2006 state that
In cases where a large number of input variables are sampled,
Robinson and Atcitty recommend using a leaped sequence, where the
...

**2**

votes

**2**answers

184 views

### Eigenvalues of monomial matrices

Let M = P*D, where P is a permutation matrix and D diagonal.
If P is also symmetric, then does M have all real eigenvalues?

**1**

vote

**1**answer

296 views

### sign-flipping inverse

Consider this matrix:
$Z=\begin{bmatrix}23.9 & -7 & -17 \\\\ -7 & 23.9 & -17 \\\\ -17 & -17 & 33.9 \end{bmatrix}$
Its inverse is entrywise negative (you can check...) and ...

**1**

vote

**1**answer

132 views

### Nonlinearly constrained optimization (quadratic)

Hi all -- what would be good methods (and/or software packages) to try for solving a problem minimizing a quadratic function $f(x) = \sum_{i=1}^N{(x_i - y_i)^2}$, where some constraints are non-linear ...

**2**

votes

**1**answer

241 views

### A question for solutions of perturbed linear systems

Consider a linear system
$$Ax=b\qquad (*)$$
and a sequence of perturbed linear systems $$(A+\delta A_n)x=b+\delta b_n. \qquad (n)$$
Suppose that all the linear systems are consistent (i.e., ...

**3**

votes

**0**answers

111 views

### Computing the norm of the columns of an implicitly defined matrix

I have an $n \times n$ matrix $M = \Sigma W$ where $\Sigma$ is diagonal and $W$ orthogonal. $W$ is implicitly defined, i.e. I can only perform matrix-vector products (but I also have access to $W^T$).
...

**2**

votes

**0**answers

381 views

### Optimal transport warping implementation in Matlab

I am implementing the paper "Optimal Mass Transport for Registration and Warping", my goal being to put it online as I just cannot find any eulerian mass transportation code online and this would be ...

**1**

vote

**3**answers

164 views

### Solving for an operator by minimization

Please note that I am looking for numerical algorithms that will tell me what the operator is that minimizes a problem.
I have a 2x2 complex hermitian operator that is a function of two variables, so ...

**0**

votes

**2**answers

322 views

### Discrete Wavelet Transform and L2 Basis

Using the mother wavlet $phi$ one obtains an orthonormal basis $\phi_{j,k}(x):=2^{j/2}\,\phi(2^j\,x-k)$of L^2 (on the unit interval say). Given a function $f$ on can calculate the coefficients using ...

**2**

votes

**0**answers

92 views

### efficient methods to do summation

Hi, is there any efficient techniques to do the following summation ?
Given a finite set $A$ containing $n$ integers $A=(x_1,x_2,…,x_n)$, where $x_i$ is an integer. Now there are $n$ subsets of $A$, ...