Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

0
votes
0answers
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
0answers
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
2answers
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
4answers
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
2answers
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
1answer
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
2answers
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
1answer
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
0answers
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
2answers
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
2answers
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
1answer
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
2answers
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
2answers
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
3answers
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
1answer
650 views

Frequency calculation using fourier transform [closed]

How to calculate the frequency of an audio file using Fourier Transform
5
votes
1answer
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
2answers
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
0answers
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
6answers
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
11answers
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
1answer
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
2answers
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
0answers
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
1answer
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
4answers
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
0answers
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
0answers
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
2answers
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
1answer
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
2answers
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
2answers
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
2answers
109 views

eigenvalues by matrix factorisation, e.g. QR

What are the origins/motivation behind that idea?
2
votes
2answers
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
2answers
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
1answer
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
2answers
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
1answer
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
3answers
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
3answers
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
3answers
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
2answers
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
0answers
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$, ...