Numerical algorithms for problems in analysis and algebra, scientific computation

**2**

votes

**1**answer

34 views

### Fixed point iteration on symmetric biconvex function

Suppose $X\subseteq\mathbb{R}^n$ is a convex set and that a function $g(x,y):X\times X\rightarrow\mathbb{R}_+$ is smooth, "strictly biconvex" (strictly convex in $x$ and $y$ independently but not ...

**-1**

votes

**0**answers

26 views

### Fast Algorithm to compute the Discrete Fourier Transform with a constraint on the summation index

I really appreciate if anyone can help me with this problem.
Problem:
Let $W_n=e^{\frac{2\pi i}{N}}$ which is the $N$th root of unity. The backward Discrete Fourier Transform of a complex vector ...

**0**

votes

**0**answers

20 views

### Weighted Perturbation Bound for Polar Decomposition

Setup: Let $X\in\mathbb{R}^{n\times r}$ be a matrix with orthogonal columns, with $\Sigma = X^TX$, and assume that $\Sigma$ is invertible (note, $\Sigma$ is not necessarily the identity).
Suppose we ...

**3**

votes

**0**answers

89 views

### Can I find the gap between the two least eigenvalues of this special matrix A(t)?

I am interested in finding the gap between the two least eigenvalues of $A(t)$, a Hermitian $N\times N$ sparse matrix whose diagonal elements are $a_it+b_i\,(1\leq i\leq N)$, and all off-diagonal ...

**3**

votes

**0**answers

51 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, ...

**0**

votes

**1**answer

233 views

### Comparing iterative methods for linear systems

For a tridiagonal matrix of the from
\begin{bmatrix}
a & -b & \newline
-b & a & -b \newline
& \ddots & \ddots & \ddots \newline
& & & & ...

**1**

vote

**1**answer

69 views

### Convergence of sequence of polynomials defined by boundary conditions

I'm sorry if my question sounds trivial, but analysis is not my field.
Consider the interval $[a,b]\subset \mathbb{R}$. On $[a,b]$, for every $n\in\mathbb{N}$, $n\ge 3$, I define the polynomials ...

**5**

votes

**1**answer

561 views

### Solution of Helmholtz-Equation where Phase is restricted by additional PDE

Hello!
Let's say I have
$(\partial_x^2 + \partial_y^2 + a)f(x,y)=0$
with $f(x,y) \in \mathbb{C}$, ($\lim_{x,y \to \infty} f(x,y)=0$).
Now separate the Amplitude and Phase of the solution:
...

**7**

votes

**3**answers

1k views

### Algorithm for the smallest (algebraic) eigenvalues of a symmetric (sparse) matrix

Hi,
I'm looking for a way to get the negative eigenspace of a large (sparse) symmetric matrix. This matrix is basically a discretized version of the operator $-\Delta + V$, $V$ negative, on some ...

**2**

votes

**1**answer

61 views

### Numerical solution of singular ODE

Consider the singular ODE
$y''+\frac{y'}{r}+p(r)y=0 \ \ with \ \ y(0)=1 \ \ and \ \ y'(0)=0$.
Theoretically such solution exists and is unique if $p$ is nice. Is there a method to numerically ...

**3**

votes

**2**answers

197 views

### Monte Carlo integration of Gaussian integrals

I was doing a physical problem, and then it comes to this Gaussian integral. The dimension of the integral is very large (dimension = 300~600), and it is difficult to find the maximum of the ...

**2**

votes

**2**answers

415 views

### Who is currently researching topics concerning applying algebraic topology and/or differential geometry to numerical methods? [closed]

I am interested in pursuing a PhD in mathematics from a top ranked university with a faculty member researching something akin to the following description: applications of algebraic topology and/or ...

**0**

votes

**1**answer

25 views

### Solving sparse linear least squares or a positive definite 5-band matrix system fast

I want to quickly solve linear least squares problem for $x \in \mathbb{R}^n$
$$min_x \left\| A x - b \right\|_2^2$$
with a special sparse structure where each row in $A$ has only up to 4 ...

**0**

votes

**1**answer

49 views

### Finding the distribution of a random variable numerically with sample data? [closed]

Just a thought that I had recently. Suppose given discrete data points for a random variable, could one numerically generate the probability function values at these discrete values? I tried looking ...

**4**

votes

**1**answer

164 views

### Special Function, Series Expansion, or Simpler Form of a Certain Infinite Product?

$\prod _{n=1}^{\infty } \left(1+a (c+n)^b\right)$ where a > 0, b < -1, and c >= 0
Is there a special function, series expansion, or other simpler (or maybe just interesting) representation of ...

**2**

votes

**0**answers

41 views

### Scale vector in scaled pivoting (numerical methods)

I'm teaching students about several numeric methods, including scaled pivoting. There's a small section in this subject that I could never find a clear explanation to, either as intuition, or a more ...

**1**

vote

**1**answer

134 views

### Using Jacobi fields to approximate parallel transport along geodesic:is the following limit true?

I apologize if this is not a research level question (already tried asking http://math.stackexchange.com/questions/1303288/relation-between-parallel-transport-and-jacobi-field-iion stack exchange with ...

**4**

votes

**1**answer

87 views

### Numerical equality testing

I am working on developing an online homework system.
One thing I would like to have is something which compares a student's answer (like $2\sin(x)\cos(x)$) with the intended answer (maybe ...

**2**

votes

**1**answer

321 views

### How to find representatives of $SL(2,\mathbb{R})/SL(2, \mathbb{Z})$

While reading about the Teichmuller flow, I am reading about the space of lattices $SL(2,\mathbb{R})/SL(2, \mathbb{Z})$.
I could not a find a good way of computing the Teichmuller flow on this ...

**5**

votes

**0**answers

158 views

### Degree of Chebyshev polynomial necessary

In general, given $0<a<1$, I want to find a polynomial $f(x)\in\Bbb R[x]$ such that $f(x)\in[1-\frac{a}2,1+\frac{a}2]$ at every $x\in[1-a,1+a]$ and $f(0)=0$. What is minimum degree that is ...

**2**

votes

**0**answers

30 views

### Finding an explicit constant in finite element error estimates

Background: In a finite element approximation to the solution of a linear PDEs, estimates on the order of convergence of the approximation to the solution rely on a theorem of Bramble and Hilbert ...

**30**

votes

**11**answers

6k 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 ...

**8**

votes

**3**answers

465 views

### Degree necessary of a polynomial?

Given $-1<a<b<0$, I want to find a polynomial $f(x)\in\Bbb R[x]$ such that $f(x)\in[a,b]$ at every $x\in[b^2,a^2]$ and $f(0)=0$. What is minimum degree that is needed and maximum degree that ...

**9**

votes

**2**answers

217 views

### Computing Gauss Legendre Quadrature for Large N

I've been scanning across the web, and haven't found a good method to compute the Gauss Legendre abscisas and weights $\{ x_j, w^j \} _j$ for large N. My question is how to do it, and why should it ...

**2**

votes

**0**answers

51 views

### Compute the smoothing of functions

Given a function $g:R^d\rightarrow R$, which is not necessarily continuous, I want to compute the "smoothing" of $g$, i.e.,
$G(\vec{y})=\int_{R^n} g(\vec{x}) f_{\vec{y}, \sigma}(\vec{x}) d\vec{x} $
...

**0**

votes

**0**answers

96 views

### Generalized arithmetic progressions contained in Bohr sets

Recall that generalized arithmetic progression of dimension $d$ is by definition a set of the form $P = P_1+\dots+P_d$, where $P_j = \{lp_j\ \mid \ |l|\leq l_j\}\subset \mathbb Z$ is an ordinary ...

**4**

votes

**2**answers

129 views

### Accuracy of the formulas for angles between almost colinear vectors

Assume $x$ and $y$ are two vectors in $\mathbb{R}^3$ and we want to compute the acute angle $\alpha\in(0,\pi/2]$ between these two (noncolinear) vectors. There are (at least) two possibilities:
In ...

**1**

vote

**0**answers

29 views

### LU growth factor applied to LDL of a Positive Semidefinite matrix [closed]

For a Positive Semidefinite matrix $A$, which we can decompose through $LDL$ decomposition as follows: $A=LDL^\text{T}$; how can we prove that for a decomposition $A=LU=L(DL^\text{T})$, the growth ...

**4**

votes

**0**answers

63 views

### Numerical integration error bounds on the unit sphere

A sequence of points $x_1,x_2,\dots$ on the unit sphere $S^{D-1}$ is said to be uniformly distributed if
\begin{align}
\lim_{N \rightarrow \infty} \frac{1}{N} \sum_{j=1}^N f(x_j) = \int_{x \in ...

**2**

votes

**1**answer

99 views

### Relation between Chebyshev Interpolation and Expansion

I am seeking connections between pointwise Lagrange interpolation (using Chebyshev-Gauss nodes) and generalized series approximation approach using Chebyshev polynomials.
Pointwise Lagrange ...

**0**

votes

**0**answers

37 views

### Global optimisation of the real part of impedance

I have the following global optimisation problem:
$$
\underset{\omega}{\min}-c^{T}\left(\omega^{2}\mathbf{1}+A^{2}\right)^{-1}b
$$
where $A$ is a $n \times n$ real matrix, $c$ and $d$ are ...

**2**

votes

**1**answer

85 views

### The bubble function

In the finite element method and more precisely the MINI element method in two dimensions, they use a function called the "bubble function" which is related to a triangle K of the space meshing and is ...

**0**

votes

**1**answer

74 views

### Upper bound for a ratio of modified Bessel functions

I am looking for an upper bound for the ratio of Bessel I functions $\dfrac{|I_\nu'(z)|}{|I_\nu(z)|}$ where $\nu$ is complex, and $z$ is a positive real number. Do you know any results about it? Thank ...

**9**

votes

**1**answer

218 views

### What happens to continuous spectrum upon discretization?

Excuse me for a bit of an vague question, but I haven't been able to find a definite answer for this for quite some time. My question is regarding (mostly non-normal )linear operators and their ...

**4**

votes

**5**answers

368 views

### What is an extragradient method?

I've searched Google, but it seems that only research journal papers appear in search results, where some new, improved, or specialized extragradient method is discussed. I've also searched Wikipedia ...

**1**

vote

**3**answers

256 views

### What are some good sanity checks for simulating BNLS?

After doing some googling, I failed to find any explicit solution for the Biharmonic Nonlinear Schrodinger Equation, which states:
$$
i\psi (x,t) _t - \Delta ^2 \psi (x,t) + |\psi (x,t) | ^{2 \sigma} ...

**2**

votes

**0**answers

40 views

### Estimating overshoot in spline interpolation

Say I have a spline space $\mathcal S$ of dimension $n$ with a set of unisolvent points $(\xi_i)_{i=1}^n$, i.e., points at which I can unambiguously interpolate within the spline space. So, given ...

**0**

votes

**0**answers

84 views

### inflow/outflow Boundary Conditions for flow in pipe

I have a question about boundary condition of solving Navier-Stokes equation through pipe.
When I simulate the flow in pipe using periodic boundary condition, it works good. But when I tried to change ...

**9**

votes

**4**answers

546 views

### Rounding errors in images of Julia sets

One typically computes Julia sets by iterating a complex function, such as a polynomial or rational function.
How do rounding errors affect the results?
I'm looking for references on this issue, ...

**6**

votes

**2**answers

205 views

### Conditions for convergence of Euler's method

It is known that a sufficient and necessary condition for
$$\dot y(t) = f(y(t), t), \quad t > 0, \quad y(0) = y_0$$
to have a unique solution is $f$ Lipschitz in $y$ and continuous in $t$. However, ...

**3**

votes

**2**answers

166 views

### What are interesting heuristics of determining how far given matrix is from a singular one?

The condition number and volume of matrix (defined as absolute value of its determinant) are things which come to mind. Is there more?
I think that over the years numerical folks (who are faced with ...

**5**

votes

**0**answers

103 views

### Hyperbolic toral automorphisms, and maximizing over orbits the minimum along an orbit of a function

Setup:
Let $\phi\colon T^2 \to T^2$ be a hyperbolic toral automorphism. Let $f\colon T^2 \to \mathbb{R}$ be a continuous function.
For $x \in T^2$, let $\underline{f}(x) = \inf_{n \in \mathbb{Z}} ...

**3**

votes

**1**answer

235 views

### Analytic Solution to SDEs

Are there any example of SDEs with constant diffusion terms, other than the Ornstein Uhlenbeck process, which have exact solutions? I'm thinking of something of the form:
\begin{equation}
dX_t = ...

**3**

votes

**1**answer

126 views

### Selecting Rays for Simulated Radon Transform

I have the task of determining approximations of a 2D function $f: (x,y)\in \mathbb{R}^2\mapsto\mathbb{R}$ from integrals along lines, i.e. from its Radon transform $R(\phi,\tau)[f(x,y)]$ and, because ...

**2**

votes

**1**answer

106 views

### cohomology algebra of submanifold in euclidean space

If we write a manifold or CW-complex $X$ as a subset of $\mathbb{R}^n$, in expression of coordinates, for example, \begin{multline}
F(S^2,k+1)=\{(x_1,x_2,x_3,\cdots, ...

**6**

votes

**4**answers

380 views

### Expected value of a function over random sets

I am doing an analysis on the complexity of some set-related algorithm where the input is a random set. One of my setbacks can be formulated as follows:
Pick $k$ distinct numbers out of numbers ...

**3**

votes

**2**answers

797 views

### algorithm for solving systems of linear Diophantine inequalities

So, I posted on stack overflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem ...

**0**

votes

**0**answers

49 views

### volterra equation of the first kind with K(0,t)=0

A standard assumption both in theory and numerical methods
for the Volterra equation of the first kind
$$ g(t) = \int_0^t K(s,t) f(s) ds$$
is that $K(s,t) \neq 0$. One can show existence of the ...

**4**

votes

**1**answer

67 views

### Numerical approximation to the Wasserstein metric?

Are there numerical methods for approximating/calculating the Wasserstein metric in particular cases?
Suppose that $f$ and $g$ are two density functions with the same support. How can I calculate the ...

**0**

votes

**0**answers

49 views

### Orthogonalization technique after cosparse dictionary update

I'm trying to adapt the cosparse dictionary learning (DL) approach described in Analysis K-SVD to a DL method that creates the dictionary as a union of orthonormal blocks (UONB).
For this I apply the ...