Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

2
votes
1answer
120 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
4answers
419 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 ...
0
votes
0answers
59 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
2answers
135 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 ...
5
votes
1answer
125 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
0answers
55 views

Bits of precision matrix reconstruction

We have a real rank $r$ matrix $M\in\{0,1\}^{n\times n}$. Suppose we have diagonalized using $LMR=D$. I want to recover a real matrix $\widetilde{M}$ such that maximum absolute entry of ...
3
votes
2answers
276 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 ...
1
vote
1answer
127 views

What is a one-parameter Newton's method?

The Newton's method that I know is defined as follows: $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$ However, I've recently encountered a paper that talks about a one-parameter family of Newton's method ...
0
votes
1answer
160 views

Generating random variables from the Cantor Distribution [closed]

I am looking for a method (exact, if possible, but at least asymptotically correct) for generating random variates from a Cantor Distribution? It seems like its abstract definition prevents this. In ...
0
votes
0answers
48 views

Comparing Calculation Error in Divergent Numerical Methods

I'm not an expert in numerical methods, but I'm doing a simulation based on non-linear differential equations (General Relativity), there solutions has singularities, thus at some points numerical ...
0
votes
1answer
83 views

What is exponentially fitted osculating straight line?

While reading an article about iterative methods for solving nonlinear equations I can't understand what is exponentially fitted osculating straight line. Could someone please briefly explain this ...
3
votes
2answers
312 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 = ...
-2
votes
1answer
559 views

BDF2 and TR-BDF2: what is better? [closed]

What method of numerical solving ODEs is better? BDF2 or TR-BDF2? Namely, what advantages has TR-BDF2 over BDF2? Is TR-BDF2 more accurate? Does it damp "ringing" better? The BDF2 method requires the ...
7
votes
1answer
223 views

Approximation theory on the disc

Chebyshev theory provides a very effective method for approximating continuous real valued functions on the unit interval. Is there something similar for continuous real valued functions on the ...
0
votes
0answers
52 views

Shooting method for non-oscillatory solutions

I am having some trouble with using the shooting method : I am given a system of ode's representing initial value problem, and I know I want one of the unknowns (=u) to vanish at infinity (which I ...
2
votes
1answer
209 views

Divergence of the Lagrange interpolation on the Chebyshev nodes

Faber theorem states that for every $\lbrace x_k^{(n)} \rbrace$ there exists a continuous $f$ function such that $\| f - L_n \|_{\infty} \not\rightarrow 0$, where $L_n$ is interpolation polynomial on ...
0
votes
1answer
135 views

A kind of Discrete Fourier Transform

Given a $z\in \mathbb{C}^N$, the DFT of $z$ is given for every $k\in [0,N-1]_\mathbb{N}$ by $$DFT_z(k)=\frac{1}{N} \sum_{j=0}^{N-1} z_j\, \omega^{-k j}$$ where I have denoted by $\omega$ the $N$-th ...
0
votes
0answers
55 views

Exact diagonalization of tridiagonal centrosymmetric matrices

It is said that one can diagonalize a tridiagonal matrix using the analytical Lanczos method http://arxiv.org/abs/cond-mat/9712283v1. In some references in it, they always say that the starting point ...
1
vote
1answer
58 views

Convergent algorithm for dividing a body into two regions of equal volume

Let $\Omega \subset R^3$ be a bounded open region. It is well known that there exists a smooth surface $\Gamma$ with minimum area and constant mean curvature which is orthogonal to $\partial \Omega$ ...
2
votes
1answer
253 views

Residues and values of Riemann Zeta function at some points

I need the following computational results for proving something. Let $1/2 + i\gamma_0$, be the first nontrivial zero of Riemann zeta function, $\zeta(s)$, i.e. $\gamma_0\sim 14.134...$. 1) what is ...
0
votes
0answers
79 views

Rational dynamical system with nonnegative paramaters

let $A$ be a rational system of the form :$\begin{cases} x_{n+1}=\frac{\alpha_{1}}{y_{n}} \\ y_{n+1}=\frac{\alpha_{2}}{z_{n}} \\ ...
3
votes
0answers
110 views

error estimate of linear interpolation in high dimension

Consider convex functions $f,g$ on $[0,1]^d$. Let $x_1,\cdots,x_n$ be $n\geq d+1$ fixed point in $[0,1]^d$ that is equally 'distributed' in the sense that $$c_1\leq ...
4
votes
1answer
202 views

Resolvent of a triangular matrix

Suppose $A$ is a triangular matrix. What is the most efficient known algorithm to compute the polynomial (in $x$) matrix $(xI-A)^{-1}$? Of course, $(xI-A)^{-1}= N(x)/p_A(x)$, where $p_A$ is the ...
-2
votes
2answers
81 views

Systems of ODEs that fulfill a matrix relationship at steady state [closed]

It is well known that for a system of linear ODE $$x'(t) = A(t) \cdot x(t) + b(t)$$ with initial condition $x(t_0) = x_0$, that for a solution at any other time point $t_1$, $x(t_1) = (z_1, \ldots, ...
4
votes
0answers
77 views

Estimating polynomial approximation error in high dimension

Question Let $x \in [-1, 1]^d \subset \mathbb{R}^d$ be a $d$-dimensional variable and assume that -- given $n$ -- I have a way of computing a polynomial $p_n(x)$ of degree $n$ that approximates a ...
0
votes
0answers
36 views

Probability of close approach for multivariate normal variables

The following problem comes from a physical model of two groups of particles in three dimensions. I need to know the probability that the two groups of particles approach each other within some ...
2
votes
0answers
72 views

What is the computational complexity to compute the integral numerically?

Given $$\int_{\Delta}\frac{P_1(x_1,x_2,\dots,x_n)}{P_2(x_1,x_2,\dots,x_n)}$$ where $P_i$ is polynomial(that is $P_1(x_1,x_2,\dots,x_n), P_2(x_1,x_2,\dots,x_n)$ are polynomial) whose coefficients are ...
1
vote
1answer
94 views

Condition Number and CFL Condition in Finite difference Methods

when applying a Finite Difference scheme for an IVP, two factors come to mind when considering stability: One factor would be the condition number of the approximation operator. The other factor ...
1
vote
0answers
148 views

Frozen coefficient method (von Neumann stability analysis)

Earlier it was considered that frozen coefficients method for Neumann stability analysis for finite difference scheme is more heuristic than rigorous. But I have read some information in a book by ...
1
vote
2answers
164 views

iterative solution better than analytic solution? [closed]

My supervisor and I were discussing a specific optimisation problem this afternoon. To be simple: solve for $R$ in the equation $Rx=y$, where $x$, $y$ are made of samples in two difference ...
8
votes
1answer
639 views

Algorithm to produce random number with a gamma distribution

I'd like to produce pseudo-random numbers with different distributions for a Monte Carlo simulation. I've got the poisson distribution working nicely with an algorithm from Knuth. I'm having trouble ...
6
votes
1answer
169 views

Computing certain integrals over high-dimensional polyhedra

Let $\delta>0$ be a small real number and consider the $k$-dimensional region consisting of points for which $$\delta\leq x_1\leq x_2\leq\ldots \leq x_k$$ and $$x_1+\ldots+x_k\leq 1.$$ I am ...
1
vote
0answers
80 views

General reparameterization of a b-spline

Say I have a bspline function (or curve) of order $k_1$, defined over some knot vector $\mathbf{t} = \{ t_i\}_1^{n_1}$, i.e. $$f(x) = \sum_i a^i B_{i,k_1}(x).$$ Do you know of a process of finding ...
4
votes
1answer
83 views

The link and equivalence between variant definition of computation model and computational complexity over reals

To unify the numerical computation and classic computability theory, or to pave a foundation for the numerical computation, mathematicians present variant computation model and computational ...
6
votes
2answers
396 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
1answer
128 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 ...
3
votes
0answers
158 views

Numerical Methods for stochastic PDE, from rough paths to backward equations

this question is about some literary references regarding the state of the art in terms of numerical methods for SPDE's. In particular, Have the numerical implications, if any, of the results in ...
2
votes
1answer
158 views

books on very large scale linear optimization

Recently in my material science research, I have encountered problems of very large scale linear optimization. I read the introductory book "Introduction to Linear Optimization (Athena Scientific ...
3
votes
3answers
208 views

Numerical solution of SDEs with colored noise

I am trying to numerically solve an SDE with both white and colored noise that models a non-linear circuit: $$ dX_t = f(X_t) dt + \sigma_w dW + \sigma_c dC $$ where $W$ is a standard Brownian motion ...
1
vote
1answer
47 views

Partial Constraint of Low Rank Matrix

Suppose $X \in \mathbb{R}^{m \times n}$ is a rank $r$ matrix. Let $\Omega$ be a generic subset of $\in \{1, \ldots, m\} \times \{1, \ldots, n\}$ of cardinality $r(m + n - r)$. Denote by $X_{\Omega}$ ...
4
votes
1answer
168 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 ...
1
vote
1answer
122 views

Could somebody recomends a good book or article about numerical methods for Stochastic Partial Differential Equations

Could somebody recomend a good book or article about numerical methods for Stochastic Partial Differential Equations. I'm looking for a good introductory material thanks.
0
votes
0answers
49 views

Numerical method for self-consistency of one-dimensional probability density function

I have an integral equation for self-consistency of one-dimensional probability density function, like this $$\rho_x(x) = \frac{1}{|a|}\int \int \rho_x\left(\frac{s-b}{a}\right) \rho_P(p) ...
0
votes
1answer
282 views

Improving Newton's Inequalities using the Taylor Theorem

Newton's inequalities say that if $f(x) = \sum \binom{n}{k} a_k x^k$ is a polynomial with all real roots then $ a_k^2 > a_{k-1}a_{k+1}$. The proof this result uses that if $f(x)$ has all real ...
2
votes
1answer
56 views

IVP accuracy - scheme accuracy Vs. derivative accuracy?

General Question: If I have an IVP with periodic and continuous initial condition, which rules the accuracy of the scheme - the manner in which we approximate spatial derivative or the acuuracy of the ...
7
votes
1answer
167 views

Compute only selected components of an eigenvector

I am wondering whether it is possible to compute portions of the eigenvectors of a given (possibly very big) matrix. More formally, consider the eigenvalue problem $\mathbf{Ax} = \lambda \mathbf{x}$, ...
7
votes
3answers
500 views

Multiprecision numerical evaluation of integral: Sage vs. PARI/GP vs. mpmath

I am trying to compute thousands of integrals of the below type, that comes up in a conformal mapping problem, to as many accurate digits as possible (preferably 50+): $$ \int_{-1}^1\textrm{d}t ...
7
votes
4answers
613 views

Numerical integration of legendre polynomials

I hope that numerical questions are also permitted here. I want to expand a smooth functions $f \in C^{\infty}$in terms of Legendre polynomials. Thus I need to calculate integrals of the form ...
2
votes
1answer
69 views

Monotonicity of Trapezoid Approximations

Here's a numerical analysis question which may not be very important, especially in practice, but has been bugging me. Suppose $f$ is a continuous function on an interval $[a,b]$. Let $T_n(f)$ be ...
-2
votes
1answer
155 views

reducing an n-order differential equation to a first order system of equations using either sagemath or sympy [closed]

I want to reduce a n-order ordinary differential equation into a first order system of equations. This is in preparation for numerical analysis. I use both Sympy and Sagemath for Computer Algebra, but ...