Numerical algorithms for problems in analysis and algebra, scientific computation

**3**

votes

**1**answer

75 views

### Numerical Evaluation of Some Triple Integral involving Negative Powers

Let $\beta_i\in (-1/2,0)$, $i=1,2,3,4$. I'm interested in obtaining numerical value of the following integrals:
$$
\int_{0<u_1<u_2<u_3<1} (1-u_1)^{\beta_1}(1-u_2)^{\beta_2} ...

**4**

votes

**1**answer

461 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:
...

**0**

votes

**0**answers

18 views

### How can one use stability analaysis of finite differences methods in linear Schrodinger to the NLS?

Specifically, I've seen a lot of analysis of grid stability for solving Linear Schrodinger with Forward Euler, Backward Euler and Crank-Nicolson. However, most of the usages I've seen for the same ...

**1**

vote

**0**answers

41 views

### Lanczos algorithm with thick restart on a dynamic matrix

currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...

**3**

votes

**2**answers

357 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 ...

**3**

votes

**0**answers

68 views

### What do we know about the generalized eigenvalue problem involving a projector?

Consider a matrix $A\in\mathbb{R}^{n\times n}$ and a projector $P\in\mathbb{R}^{n\times n}$.
Are there results regarding the generalized eigenpairs $(v,\lambda)$ of the generalized eigenproblem
...

**4**

votes

**1**answer

562 views

### Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)

Update #6:
Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer Are runtime bounds in P decidable? Answer: No.
Emanuele's answer illuminates (for me) Luca Trevisan's ...

**8**

votes

**1**answer

261 views

### Fast checking that overdetermined polynomial system does not have a solution

As a result of some inductive procedure for each $n$ I have a system of about $n^2$ polynomial equations with $n$ variables with integer coefficients, which can be precisely computed. As the system is ...

**-1**

votes

**1**answer

687 views

### Determine noise distribution [closed]

I'm trying to solve the following least squares problem:
$\underset{x}{\text{min}} ||Ax - \tilde{b}||_2$
where $Ax = b$ and $\tilde{b} = b + w$
Question:
How do I determine which probability ...

**0**

votes

**1**answer

60 views

### Convergence for symmetric, positive semi-definite operator

Assume $u$ is a vector in the Euclidean space $\mathbb{R}^N$, $\|u\|=\sqrt{\langle u, u\rangle}$, where $\langle u, v\rangle = \sum_{i=1}^N u_i v_i$.
I have that $\|u^{k+1}-u\|\leq \|I - c ...

**8**

votes

**1**answer

151 views

### Sharpest bound on the zero free region of $\zeta^{\prime}$?

I'm interested in calculating all of the zeroes of the first derivative of the Riemann $\zeta$ function up to an arbitrary height. I know that (on the RH), all of these zeroes will have real part $\ge ...

**3**

votes

**1**answer

101 views

### Approximate the square root of (1-X) efficiently through (nested) products

Currently, I encountered a problem of approximating the following
series:
$$
(I-X)^{-\frac{1}{2}}=I+\frac{1}{2}X+\frac{1\cdot3}{2\cdot4}X^{2}+\frac{1\cdot3\cdot5}{2\cdot4\cdot6}X^{3}+\ldots
$$
where ...

**8**

votes

**1**answer

132 views

### is there any such result about Bernstein polynomials?

It is well known that for any lipschitz function $f:[0,1]\rightarrow [0,1]$, we can approximate it
by $\sum_{i=1}^n f(i/n) {n\choose i} x^i (1-x)^{n-i}$, and the $L_\infty$ error is $O(1/\sqrt{n})$. ...

**2**

votes

**2**answers

261 views

### What is the definition of an antilimit?

I've seen some references to antilimits in the numerical analysis literature, but no definition of the term. The impression I get is that in specific contexts where every sequence $x_0,x_1,x_2,\dots$ ...

**4**

votes

**1**answer

1k views

### Upper bound on largest eigenvalue of a real symmetric n*n matrix with all main diagonal >0, everywhere else <=0

Is there a good analytic upper bound on the largest eigenvalue of a real symmetric n*n matrix with all main diagonal entries strictly positive, all other entries <=0 with typically many of them ...

**1**

vote

**0**answers

65 views

### Is there an example where the error of Gauss-Laguerre quadrature does not vanish?

The $n$th Gauss-Laguerre quadrature aims to approximate integral $$\int_{\mathbb{R}_+} f(x) \exp(-x)$$ by the sum
$$\sum_{i=1}^n f(x_i) w_i$$
where $x_1,...,x_n$ are the roots of the $n$th Laguerre ...

**1**

vote

**3**answers

241 views

### What are the basis functions for a product space?

Let $X=L^1\left([0,1]^3\right)$,
for numerical purpose, what are the possible basis function for $X$?
In finite element method, the basis functions are tooth functions, or polynomial functions.
Is ...

**2**

votes

**0**answers

81 views

### Stationary Distribution for Markov-like system?

Let
\begin{equation}
A=
\begin{pmatrix}
0 & a_{1,2} & a_{1,3} \\
a_{2,1} & 0 & a_{2,3} \\
a_{3,1} & a_{3,2} & 0
\end{pmatrix},
\end{equation}
\begin{equation}
B=
...

**0**

votes

**0**answers

47 views

### ODE system with a very large number of equations

Are there any theory about a ode system (linear or nonlinear) with a very large number of equations, e.g. more than $10^5$ equations ?

**5**

votes

**5**answers

443 views

### solving series of linear systems with diagonal perturbations

I would like to solve a series of linear systems Ax=b as quickly as quickly as possible. However, the systems are related. Specifically, each matrix A is given by:
cI + E
where E is a fixed sparse, ...

**3**

votes

**1**answer

88 views

### Trace of multiplied positive definite matrices

I have to compute $Tr(K^{-1}\Sigma)$ where both $K$ and $\Sigma$ are symmetric positive definite matrices.
Question is considering that I have computed the Cholesky, $L_1$ of $K$ previously, is there ...

**9**

votes

**4**answers

692 views

### Is Gauss-Seidel guaranteed to converge on *semi* positive definite matrices?

I know that the Gauss-Seidel method is guaranteed to converge given that the matrix you want to solve is positive definite. I've looked at the proofs of convergence, and it appears that one cannot ...

**1**

vote

**2**answers

80 views

### Numerical calculation of Fourier transform with a nice error bound

I'd like to have an algorithm for a numerical calculation of Fourier transform with a nice error bound. To be precise, if $f$ is a function from $L_1(R)$, $F[f]$ is it's exact Fourier transform and ...

**0**

votes

**0**answers

101 views

### solving a system of algebraic equations

I'm trying to solve the following system of nonlinear algebraic equations for $q_{e}\in\mathbb{R}^{4}$
$$
...

**0**

votes

**0**answers

46 views

### Generalized Eigenvalue problem solution

$\circ$ Consider the following eigenvalue problem : $$XY^{T}YX^{T}w=\lambda XX^{T}w \hspace{0.5cm} (1)$$
Matrices $XY^{T}$ and $XX^{T}$ $\in \mathbb{R}_{n \times n}$ are positive semi-definite and ...

**10**

votes

**1**answer

287 views

### Who is Petrov of the Petrov-Galerkin method?

I was not able to find the origin of the name Petrov in the Petrov-Galerkin method for the numerical approximation of PDEs.
Wikipedia refers to a certain Alexander G. Petrov, but it is still not ...

**1**

vote

**0**answers

94 views

### Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix

I am looking mainly for implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers.
To be precise, I want ...

**30**

votes

**7**answers

2k views

### What is the time complexity of computing sin(x) to t bits of precision?

Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference?
Long version of the question:
I'm sort of surprised to be asking this, because ...

**2**

votes

**2**answers

100 views

### Seeking a class of functions for which sums approximate integrals well

Is there a "natural" class of integrable functions $f: {\mathbb R} \rightarrow {\mathbb R}$ for which it is true (and, preferably, not too hard to prove!) that $\sup_{0 \leq a < h} |h S(a,h) - I|$ ...

**3**

votes

**3**answers

3k views

### Finding the length of a cubic B-spline

Can I find an analytical solution to the the length of an 2-dimensional cubic B-spline? All I can find are chorded approximations and the opinion that the analytic solution is "unbearably gruesome". ...

**4**

votes

**0**answers

85 views

### Error of midpoint method for differentiable functions

Is it the case that for every differentiable function $f$ on $[0,1]$ (with finite one-sided derivatives at the endpoints), the midpoint method of estimating $\int_0^1 f(x) \: dx$ has error $o(1/n)$?
...

**3**

votes

**1**answer

169 views

### Error of midpoint method for functions that are not twice-differentiable

All of the bounds I've seen for the error of the midpoint method of integration are expressed in terms of the second derivative of the function. What bounds are available when the function is not ...

**0**

votes

**1**answer

104 views

### How to determine the distance between two matrices under the meaning of a matrix function? [closed]

Suppose a nonlinear infinitely continous differentiable function $f:\mathbb{D}\mapsto \mathbb{R^+}$, where $\mathbb{D}\subset\left\{X|\text{rank}{X}=2,X\in\mathbb{R}^{3\times 3}\right\}$ is a ...

**1**

vote

**1**answer

99 views

### Is there any geometric and intuitive interpretation of Newton-like iterative steps in numerical optimization?

Are the iterative steps in optimization affected by the intrinsic and extrinsic curvatures of the objective functions ? and How?
Is there any geometric and intuitive demo show illustrating the ...

**3**

votes

**1**answer

61 views

### Delay Differential Equations Numerical methods

I have a general question about delay differential equations. I know that even simple ones hardly have analytic solutions and mine clearly doesn't have any as it is a system of non-linear delay ...

**0**

votes

**0**answers

53 views

### unique positive real root fast computation

What is the fastest way to compute the value of the unique positive real root corresponding to the following polynom:
:p(x) = a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x - f = 0
where a, b, c, d, e, f are ...

**13**

votes

**1**answer

776 views

### Who introduced the notion of “stability” in numerical analysis?

I am preparing a lecture course on the applications of operator theory where I intended to make some numerical analysis application. I was wondering about this question while browsing the literature I ...

**1**

vote

**1**answer

60 views

### Quadrature rules exact for given functions

Many quadrature schemes are defined by the degree of polynomials for which they are exact. For example, we say that the rule SUM_i a_i f(x_i) is order n when SUM_i a_i p(x_i) = INT p(x) dx for all ...

**5**

votes

**2**answers

507 views

### Runge-Kutta method with c<1

In trying to solve an ODE $y'=f(y,t)$ with a function f that is discontinuous at a subset (codim=1) of $\mathbb R^n$, I am looking for a Runge-Kutta ODE method whose stages do not evaluate $f(x,t)$ at ...

**-1**

votes

**2**answers

102 views

### Does an implicit Runge Kutta scheme applied on a nonlinear ODE give a nonlinear set of equations to solve in each step?

We want to approximately solve an ODE
$$\frac{dy}{dt} = f(y,t)$$
with the Runge Kutta method
$$y_{n+1} = y_n + h \sum_{i=1}^s b_i k_i$$
$$k_i = f\left(y_n + h \sum_{j=1}^s a_{ij} k_j,\,t_n + c_i ...

**3**

votes

**1**answer

116 views

### approximation methods in integral equations

Recently I was reading about integral equations and I am a beginner in it. There was a constant reference to the non-availability of methods to find the exact solutions and hence lot of approximation ...

**12**

votes

**1**answer

1k views

### The unreasonable effectiveness of Pade approximation

I am trying to get an intuitive feel for why the Pade approximation works so well. Given a truncated Taylor/Maclaurin series it "extrapolates" it beyond the radius of convergence. But what I can't ...

**4**

votes

**0**answers

97 views

### Linearizing and solving a nonlinear PDE numerically

Im trying to solve the following (transport & diffusion) nonlinear PDE numerically (via finite volume on a cuboid region. Some Material gets cooled down, s.t. in some areas the material becomes ...

**14**

votes

**8**answers

2k views

### Exponential of large matrices

I want to make a diffusion kernel, which involves $e^{\beta A}$, where A is a large matrix (25k by 25k). It is an adjacency matrix, so it's symmetric and very sparse.
Does anyone have a ...

**4**

votes

**0**answers

261 views

### What are the eigenvectors of the Lagrange interpolation matrix?

Let $F$ be a field.
Let $x_1,\ldots,x_k,y_1,\ldots,y_k\in F$ be distinct elements in the field.
Consider the $k\times k$ matrix that in position $i$, $j$ has the element
$\frac{\prod_{l\neq i}(y_i - ...

**0**

votes

**1**answer

474 views

### randomized SVD singular values

randomized SVD decomposes a matrix by extracting the first k singular values/vectors using k+p random projections.
my question concerns the singular values that are output from the algorithm. why ...

**2**

votes

**2**answers

949 views

### Finding the formula for Bezier curve ratios (hull/point : point/baseline)

Given a cubic Bezier curve defined by points p₁, p₂, p₃, and p₄, a point B on that curve at some t value (where 0 ≤ t ≤ 1), a point A on the line (p₂ — p₃) at distance ratio t from p₂, and a point C ...

**4**

votes

**1**answer

115 views

### Local positivity of solutions to linear differential inequalities (Chaplygin's theorem)

According to the entry "Differential inequality" of the Encyclopedia of Mathematics
http://www.encyclopediaofmath.org/index.php/Differential_inequality
the following result is due to Chaplygin ...

**0**

votes

**0**answers

23 views

### B-spline re-parametrization

I have a question regarding the re-parameterisation of a B-spline.
Some info:
The B-spline is of order 4 (degree 5), hence $C^3$ continuity
There is no knot multiplicity
The end conditions are not ...

**0**

votes

**1**answer

60 views

### Estimating the vector potential

My question is, that given a vector field only numerically discrete in space, is there a way to estimate its vector potential?
Theoretically, I see this which requires the vector field over all of ...