Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

1
vote
1answer
83 views

Estimating the volume of a union of balls

Let $\{ B_i \}_{i=1}^n$ be a set of $n$ ball in the unit cube $C$ of dimension $d$. If I want to estimate $$ \frac{ \lambda \left( \cup B_i \right) }{\lambda\left( C \right) }, \tag{1} $$ where ...
2
votes
2answers
136 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
0answers
130 views

open problems in Numerical Analysis [on hold]

There are plenty of open problems in Graph Theory, Number Theory, and Combinatorics, according to the Open Problem Garden: http://www.openproblemgarden.org/. Yet there are no open problems in ...
1
vote
1answer
58 views

Real solutions for systems of monomial equations

I have a $K$ equations of the form $x_1^{a_{i1}} \cdots x_n^{a_{in}}=c_i$ where $a_{ij}$ are non-negative integer constants and $c_i$ are real constants -- i.e. each equation is a monomial in $n$ ...
2
votes
3answers
127 views

Estimating the Variance of a Discrete Normal Distribution

Let $f(x; \sigma) = \frac{1}{\sigma\sqrt{2\pi}}\cdot e^{-\frac{x^2}{2\sigma^2}}$ be the probability density function of a normal distribution $\mathcal{N}(0, \sigma^2)$. We consider a discrete normal ...
7
votes
2answers
816 views

Why are there so few zero-dimensional polynomial system solvers and is this because there is no real market for them?

My questions involve the quotes below from wikipedia regarding solving polynomial systems, which given the size of the market for Big Data & Predictive Analysis applications I find puzzling: ...
1
vote
0answers
81 views

Asymptotic expansion of an integral, related to Maass forms

I am trying to compute the asymptotic expansion of the integral $I(t) = \int_{C} e^{\sqrt{1+u}(\frac{1}{t}+\frac{t^2}{\sqrt{u}})}\frac{u^\eta}{\sqrt{1+u}}du$ as $t$ is real and $t\rightarrow +\infty$, ...
8
votes
1answer
320 views

Gaps between roots of trigonometric polynomials

[Cross-posted from Math.SE because I got no responses there.] Given a polynomial in $e^{\mathrm{i}k t}$ of the form $$ p(t) = \sum_{-n\leq k\leq n} c_k e^{\mathrm{i}k t} $$ with $\bar c_{-k} = c_k$, ...
4
votes
1answer
66 views

Sensitivity of the range of a matrix

The distance between two subspaces $\mathcal{U}$ and $\widetilde{\mathcal{U}}$ is classically defined as $d(\mathcal{U},\tilde{\mathcal{U}}):=\|P-\tilde{P}\|$, where $P$ and $\tilde{P}$ are orthogonal ...
2
votes
2answers
95 views

Boundedness of ratio of linear functions

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
2
votes
0answers
115 views

Are there workable numerical approaches for the pentagon equation?

Warning: this post is the "numerical" analog of Are there workable algebraic geometry approaches for the pentagon equation? I've replaced "algebraic geometry" by "numerical" in its content, ...
8
votes
4answers
245 views

Software tools for medium-scale systems of polynomial equations

I am attempting to find all real solutions of a system of 12 polynomial equations in 12 unknowns. The equations each have total degree 6 and contain up to 1700 terms. I am only interested in real ...
7
votes
1answer
218 views

Compute an arbitrary decimal place of $\pi$

Is there a method to find the value of the $n$-th decimal place of $\pi$ which is more efficient than having to compute all decimal places before as well?
1
vote
1answer
52 views

Finite differencing scheme for Hamilton's equation with planar linkages

I am trying to simulate the movement of a planar linkage in the plane whose position and momentum obey Hamilton's equations, which is to say that $${{dq}\over{dt}} = {{dH}\over{dp}}$$ and ...
1
vote
1answer
87 views

Are there some algorithms to solve the diagonal matrix $X$ to the following matrix equation?

Suppose $X$ is an unknown $m \times m$ diagonal matrix. Given a scalar $0<c<1$, and a matrix $A$ of $m \times m$ size whose entries $0<A_{i,j}<1$. Are there some algorithms to find the ...
2
votes
1answer
100 views

Projection onto $\ell^{2,1}$ ball

Does anyone have an idea how to project onto the $\ell^{2,1}$ ball efficiently, i.e. how to solve $$ u = \arg \min_u \|u-f \|^2 \text{such that } \left(\sum_i \big(\sum_j |u_{i,j}|\big)^2 ...
3
votes
1answer
70 views

Advice on numerical solution for 2D hyperbolic PDE with zero flux boundary conditions

I would like to numerically solve a hyperbolic PDE of the form $\frac{\partial\theta_t}{\partial t}(x,y)+\frac{\partial\left[\theta_t \gamma_t^x\right]}{\partial x}(x,y)+\frac{\partial\left[\theta_t ...
1
vote
1answer
136 views

Solving a matrix equation $X=c \cdot AXA' +I$ with a diagonal corrections

I am now struggling to solve the matrix $X \in R^{n \times n}$ in the following equation: $X=c \cdot AXA' - diag(c \cdot AXA')+ I$, where (1) $A \in R^{n \times n}$ is a given matrix whose element ...
2
votes
1answer
68 views

Discrete gradient on point clouds

I am interested to know some ways to approximate discrete gradient if you have a function on point clouds in 2D or 3D. If you have a function defined on a grid, it well known that you can use a ...
4
votes
1answer
72 views

Explicit probability conserving solvers for Pauli equation?

I know that there exist probability conserving explicit solvers for time-dependent Schrödinger's equation, for example, Visscher's one. But when I tried to add spin into account in this scheme, it ...
2
votes
1answer
96 views

Roots of modified polynomials

Consider the following two polynomials: $$ g=x^3 - x^2 - (c + 2)x + c $$ and $$ h=x^3 - x^2 - cx + c $$ The roots of $h$ are $1$ and $\pm \sqrt{c}$. I am interested in obtaining the roots of $g$, ...
0
votes
0answers
24 views

Why Does a quadratic phase term in BNLS causes collapse?

I've heard a couple of times that in the Biharmonic Nonlinear Schrodinger Equation, $i\psi_z + \Delta ^2 \psi + |\psi | ^{2\sigma } \psi =0 $, $\psi (x, 0) = \psi _0 (x) \in H^1( \mathbb{R} ^d ) $ ...
6
votes
1answer
127 views

Estimates of Hausdorff dimension (and its derivatives)

For example, the cookie cutter maps, say $T:I_1 \cup I_2 \subset [0,1] \to [0,1] $ is a $C^2$ map such that $|T'|>1$ and provided $I_1$ and $I_2$ are disjoint closed intervals and $T(I_i)=[0,1]$. ...
1
vote
0answers
43 views

interpolation and approximation [closed]

Given a function $f$ in C^k[a,b], can we always construct function $g \neq f$ such that $g(x) \ge f(x)$ for all $x \in [a,b]$, $f^{(m)}(a)=g^{(m)}(a)$ and $f^{(m)}(b)=g^{(m)}(b)$ for $m=0,1,\dots, k$ ...
5
votes
2answers
368 views

How to estimate the Haar measure on $G_2$

I have a sequence of real numbers. I want to know whether this sequence looks like the traces in the standard representation of a random sequence of elements of $G_2$. (Here random is according to the ...
3
votes
0answers
97 views

Rank 1 Approximation of Elementwise Inverse Matrix

I'm wondering whether there is a good way to solve the following optimisation problem. Given a strictly positive quadratic matrix $A$, find two diagonal matrices $D_1$ and $D_2$ so that $$ \| D_1 A ...
1
vote
0answers
76 views

Bounds for the infinity norm of the inverse for certain diagonaly dominant matrices

I m trying to analyse the stability against perturbations for a specific system of linear equations $Ax=b$. For this, i use the standard condition number $||A||_{\infty}||A^{-1}||_{\infty}$. Here ...
1
vote
0answers
43 views

Using FFT to aproximate a fuction [closed]

I am trying to use the FFT to approximate a given function. So i have 10 points xk that are given for example, if i use the FFT that will give me Xk. So now using the inverse FFT we can get the ...
1
vote
3answers
139 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} ...
3
votes
3answers
118 views

Quadrature formula max accuracy

I'm looking for a maximum accuracy quadrature formula: $$ \int_{-1} ^{1} \sqrt{\frac {1-x}{1+x}} f(x)dx = A_1f(x_1)+A_2f(x_2)+R(f) $$ I don't know exactly if it's Trapezoidal rule which has the ...
0
votes
1answer
69 views

Decompositions of sparse symmetric matrices and methods for solving large linear equations

I am writing code for solving linear equations of the form $$A_{n\times n}\cdot x=1_n$$ where $n$ is on the order of $10^6$ and $A$ is a symmetric matrix with approx $10^3$ nonzero entries in each ...
2
votes
1answer
72 views

An algebraic equation question [closed]

My question is this: If $\frac{\sqrt[n]{\prod_{i=1}^n(p_i + 1)}}{\sqrt[n]{\prod_{i=1}^n(m_i + 1)}} = e ^\beta$ can I find an expression (either exact or approximate) for ...
2
votes
1answer
93 views

Polynomial upper and lower bounds

Consider approximating smooth function $f(x): \mathbb{R} \to \mathbb{R}$ over the interval $[a,b]$ with a bounded $k$th derivative over the interval. I would like to find degree $d$ polynomials ...
3
votes
1answer
128 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} ...
0
votes
0answers
34 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
0answers
61 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 ...
8
votes
1answer
287 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
1answer
79 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
1answer
186 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
1answer
126 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
1answer
177 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})$. ...
1
vote
1answer
148 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 ...
2
votes
0answers
95 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= ...
3
votes
1answer
97 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 ...
1
vote
2answers
102 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
0answers
117 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}$ $$ ...
3
votes
0answers
73 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 ...
2
votes
0answers
116 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 ...
2
votes
2answers
116 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|$ ...
4
votes
0answers
88 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)$? ...