Questions tagged [approximation]

A method of finding nearly-optimal solutions to a problem. Generally, this terminology is applied to algorithms and heuristics for solving NP-Hard problems in computer science.

Filter by
Sorted by
Tagged with
3 votes
1 answer
75 views

Robust ways of evaluating $j_n(x+iy)/e^y$

For reasons to do with extending the range of applicability of this Mathematica package, I would like to have a good handle on the numerical evaluation of functions of the form $$ f(x) = \frac{j_n(\...
user avatar
9 votes
2 answers
225 views

Efficiently estimating trace of a product of matrices

I have $d\times d$ real-valued matrices $A_1,\ldots,A_k$, $1000<d<4000$, $k\approx 50$, and need to estimate the trace of the following matrix product $$t=\text{tr}(A_1 A_2\cdots A_k A_k^T \...
user avatar
6 votes
1 answer
156 views

General approach to infinite sums

My question is specific to algorithms and models of computation. I would like to write code to evaluate the following expression quickly and accurately: $$\log \left( \sum_{i=1}^{\infty}{I_{\nu+i}(2\...
user avatar
  • 163
1 vote
0 answers
116 views

Fast evaluation of trigonometric polynomials

Suppose you have a trigonometric polynomial of the form \begin{equation*} x(t) = \sum_{k = 0}^N a_k \cos(2 \pi k f_0 t). \end{equation*} Using Clenshaw algorithm, one can evaluate this polynomial in $...
user avatar
1 vote
0 answers
40 views

elementwise function of low rank approximation

I recently ran into an interesting result. I have a matrix $D$ containing pairwise distances between all points in a dataset. This matrix is converted to a similarity matrix $S$ via an RBF kernel. ...
user avatar
  • 1,169
1 vote
1 answer
159 views

Improving function approximation with neural network

I am building a neural network to approximate a data set which takes 3 inputs and gives 1 output. After testing the network using a few different iterations of hidden layers and adjusting optimizers ...
user avatar
  • 27
0 votes
0 answers
102 views

Boundary conditions for an FEM approximation of the Laplace operator

Using FEM, I want to approximate the Laplacian $$u = \nabla \cdot \nabla h \, ,$$ where $h(x,y)$ is an FEM approximated scalar field on the same mesh, i.e. piecewise differentiable. I am using MOOSE ...
user avatar
  • 1
5 votes
1 answer
195 views

Floating point and global error in Euler Method

Inspired by this answer, I tried to understand when floating point errors come into visibility and to check it also comparing the plot of the numerical solution with Explicit Euler with the analytical ...
user avatar
  • 289
3 votes
1 answer
75 views

Is there a source/cookbook of equations that approximate geometric shapes?

I'm numerically modelling flows around various geometric 2D shapes. Is there a good source/cookbook of equations that approximate these? Some examples are Rectangle: $(x-a)^n+(y-b)^n < r^n$ where ...
user avatar
  • 81
4 votes
0 answers
59 views

Continuous limit and nonlinear functional analysis

I have a kind of general question about approximation schemes in nonlinear functional analysis. Given a nonlinear map $\Phi$ from an open set (in an infinite dimensional Banach space) of functions to ...
user avatar
  • 141
1 vote
0 answers
73 views

Error curve does not oscillate in between reference points using Remez

Using the Remez algorithm, implemented using multi-precision library, in certain functions that I want to approximate, the error curve does not oscillate in between reference points, and so no roots ...
user avatar
  • 161
2 votes
1 answer
78 views

Linearization of Remez algorithm rational case

In the rational case, we are interested to find polynomials $P(x)$ and $Q(x)$ s.t. $f(x_k)-P(x_k)/Q(x_k)=(-1)^kE$ for $k=1,2,\ldots, N$ where $N=deg(P)+deg(Q)+2$ This can be rewritten as $$ (1)~~~~~~(...
user avatar
  • 161
1 vote
1 answer
68 views

Questions on Daubechies wavelets

Is the refinement equation for the orthonormal Daubechies scaling function $$\phi(x) = \sqrt{2} \sum_n h_n \phi(2x-n) \;?$$ The filter coefficients for Daubechies wavelets have been given e.g. in this ...
user avatar
  • 331
2 votes
0 answers
126 views

Remez algorithm convergence

I have implemented the Remez algorithm in Python where all calculations were done with the Python mpmath library. I have noticed that sometimes the $|E_{max}|$ and $|E_{min}|$ do not monotonically ...
user avatar
  • 161
3 votes
3 answers
332 views

What are some algorithms to calculate the width of an arbitrary polygon when a bounding box approximation is inaccurate

What are some alternative algorithms to creating a bounding box for finding the max width of a concave, simple winding polygon, like the one in the below image? I prefer solutions that are more ...
user avatar
  • 131
1 vote
1 answer
922 views

what is non-asymptotic convergence?

I guess convergence in general means it is in asymptotic sense but what does non-asymptotic convergence mean?. Can someone please explain with an example?
user avatar
2 votes
0 answers
30 views

Fast approximate evaluation of Fourier-Legendre series

Suppose I know that a function from $[0,\pi] \to \mathbb{R}$ may be written as $$ \sum_{k=0}^\infty A_l \frac{2l+1}{4\pi} P_l(r) $$ where $A_l$ all are known. Is there a way in which I may very ...
user avatar
  • 21
0 votes
2 answers
281 views

How can I calculate the exponential integral?

(I originally asked this in a different exchange.) I'm writing a program that uses the prime-counting function. Right now, I'm using x/log(x), but I want to ...
user avatar
  • 109
5 votes
1 answer
79 views

approximate function such that the inverse of the approximation is "simple"

I have a smooth enough injective function $f:[a, b]\to \mathbb{R}$ which I want to approximate by something that can be computed quickly, e.g., a Padé approximant of low degree, $$ \frac{\sum_{j=0}^m ...
user avatar
4 votes
0 answers
80 views

Fast approximate solver for vehicle routing problem

I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is ...
user avatar
  • 141
4 votes
0 answers
201 views

MATLAB: Compute the Schwarz-Christoffel transformation symbolically

Suppose we have a conformal mapping from the unit disk in the $\omega$ plane onto the exterior of a polygon in the $z$ plane. The Schwarz-Christoffel mapping in this case is defined as: $$f(u) = A - ...
user avatar
  • 73
8 votes
1 answer
282 views

Size of jump for piecewise discontinuous approximations

If one has a sufficiently smooth function $u$ that is approximated by a piecewise constant function $u_h=\Pi^0_h u$ on a mesh of cell size $h$ (where $\Pi^0_h$ is the $L_2$ projection onto the ...
user avatar
0 votes
1 answer
43 views

Slightly change two vectors to satisfy a constraint

$\vec{a}\cdot\vec{b} \approx c$ $\vec{\alpha} \cdot \vec{\beta} = c$ $\vec{\alpha}$ is close to $\vec{a}$ and $\vec{\beta}$ is close to $\vec{b}$ Given $\vec{a}$, $\vec{b}$ and c, how to find $\vec{\...
user avatar
  • 163
7 votes
1 answer
324 views

What algorithm does (or did?) Excel use for Bessel functions that is discontinuous at x=8?

Writing this comment reminded me of something I noticed years ago about evaluating Bessel functions of the first kind $J_n(x)$ in Excel. (BESSELJ) I don't use Excel now but at the time I'd checked ...
user avatar
  • 842
2 votes
0 answers
66 views

Weighted Set Cover in practice, beyond the greedy algorithm

According to the wikipedia page for Set Cover, the greedy algorithm for weighted set cover achieves the polynomial-time approximation bound. There are other techniques for solving Set Cover, such as ...
user avatar
  • 251
1 vote
1 answer
144 views

Approximation of a non linear problem with python

I need your help to solve a problem I'm working on for school. My goal is to approximate the coefficients of a weight matrix so that they check particular properties. So I have $W$ the weight matrix ...
user avatar
3 votes
2 answers
277 views

Image hash similarity matching possible?

I have the following question: We have two face image files (JPEG), a Matrix of $128\times 128$ with values between 0-255. We would like to hash both image files using a function $f(x, key)$. Where I ...
user avatar
  • 131
3 votes
1 answer
154 views

Taylor expansion of error - Finite elements approximation

In some of my computations I calculate a scalar value $\lambda_h$ (in my case an eigenvalue) depending on a finite element discretization of the domain. Usually we can manage to find estimates of the ...
user avatar
0 votes
1 answer
85 views

Which are some good algorithms and heuristics to calculate the similarity between two matrices?

Say I have a matrix like this: \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{bmatrix} And this one: \begin{bmatrix} ...
user avatar
  • 109
0 votes
1 answer
231 views

Linear Least-Squares Point-to-Plane ICP degenerative case

I'm trying to implement Linear Least-Squares Optimization for Point-to-Plane ICP Surface Registration Paper describes linear approximation for point to plane distance for rigid ICP. This approach is ...
user avatar
  • 215
0 votes
1 answer
76 views

Chebychev Polynomial derivatives at zero points and extreme points

I was looking for some help with derivatives of Chebychev polynomials at zero points. The recursive expression, $$ T_{(j+1)}(x) = 2xT_j(x) - T_{(j-1)}(x) $$ has the derivative $$ T'_{j+1}(x) = 2T_j(...
user avatar
0 votes
1 answer
2k views

Derivatives of a Chebychev polynomial

I am using Chebychev collocation nodes for approximation, and my problem requires me to calculate derivatives of the polynomial. I have been reading from a few sources, but I am not sure I understand ...
user avatar
1 vote
0 answers
64 views

Computing dilogarithm

I'm measuring the integral of a quantity which, mathematically, requires the computation of a dilogarithm function. $$\operatorname{Li}_2(be^{ax})$$ where $b$ and $a$ (are real and) can be positive ...
user avatar
0 votes
1 answer
256 views

B-Splines Matlab Package

I'm looking for a good Matlab package/library for B-Splines approximation. Ideally, it would take knots $t_1, \ldots , t_n$, and data points $g(t_1),\ldots , g(t_n)$, and Produce $$Vg :\,= \sum\...
user avatar
4 votes
0 answers
88 views

Extrapolation after successive finite element refinement

I wish to compute a certain function $\lambda$ (in my case an eigenvalue of the Laplacian) to a certain accuracy, which I wish to guarantee, if possible. I started with a finite element method. I know ...
user avatar
4 votes
1 answer
827 views

Chebyshev approximation by projection vs interpolation

Suppose we want to approximate a function $f: [a, b] \rightarrow \Re$ with a Chebyshev series: $$ f(x) \approx \sum_{k=0}^n c_k \, T_k\left( \frac{2x-b-a}{b-a} \right) $$ where $T_k(x) = \cos(k\, \...
user avatar
  • 161
4 votes
1 answer
214 views

Numerical evaluation of the Exponential Integral Ei by rational Chebyshev approximations fails

I am trying to evaluate the Exponential Integral $Ei(x)=-\int^{\infty}_{-x}\frac{e^{-t}}{t}dt$ for $x>0$ (interpreted as the Cauchy principal value) by using rational Chebyshev approximations, ...
user avatar
  • 155
1 vote
0 answers
37 views

Find alternative path closest to original

I have a set of points in a 2D space. I want to connect the outer points so I get the convex hull. The problem here is that there is a limit to the distance between two points. Let me clarify that ...
user avatar
1 vote
1 answer
58 views

Finding optimal point distance to get desired number of random points in an area

I have a random point generator which takes a distance $d$ and fills an area with points such that distance between any two points is no less that $d$: I need to control the number of points in the ...
user avatar
  • 383
5 votes
1 answer
435 views

Polynomial order of an approximation of a section of sine and numerical accuracy

I was playing with the idea that a sine function is periodic. But even within one period there are symmetries, namely the second fourth of a period is the mirror image of the first fourth and the ...
user avatar
  • 430
2 votes
1 answer
3k views

imaginary time propagation to find ground state wavefunction

I understand the basic idea of imaginary time propagation method: The wavefunction $\psi(x,t)$ as a superposition of energy eigenstates $\phi_m(x)$: $$ \psi(x,t)=\sum_m \phi_m(x)e^{-iE_mt/\hbar} $$ ...
user avatar
  • 153
1 vote
0 answers
49 views

Alternative to two "for" loops in finding best neighborhoods for TSP?

I am trying to solve Travelling Salesman Problems using tabu search. I have been able to successfully find "near enough" optimal solutions (as well as one optimal, yay!). For the moment I am using ...
user avatar
4 votes
2 answers
468 views

Interpolation with the roots of orthogonal polynomials & Spectral expansion

I'm a bit confused about the relationships between these two approximation methods mentioned in the title. Does this kind of interpolation also belongs to the field of spectral methods? Are the ...
user avatar
  • 639
3 votes
2 answers
2k views

Methods for fast approximation of convolution

What are the state of the art methods for fast 2D convolution approximation? I'm familiar with SVD based multiplication and cross approximation approaches, but would be thankful to get additional ...
user avatar
  • 83
5 votes
0 answers
135 views

Are there any benefits of computable analysis to numerical algorithms

Computers can work only with computable numbers, while most of the algorithms are based on analysis of real numbers (real analysis). When I heard of the existence of computable analysis I ...
user avatar
  • 607
6 votes
1 answer
287 views

Does this Algorithm (probably Fourier like) Exist for 2D Shapes? [closed]

Update: Someone changed the title to this post to a possible answer ("Fourier decomposition of parametric shapes") but I changed it to a different title as that makes it clear what I was asking. As I ...
user avatar
1 vote
1 answer
75 views

Expected number of steps before a global optimum is found with Simulated Annealing

I'm reading a technical report on Simulated Annealing: On the Convergence Time of Simulated Annealing, by Sanguthevar Rajasekaran. You may find it following this link. Given $G=(V, E)$ is the graph ...
user avatar
  • 113
6 votes
2 answers
4k views

Solving a system of linear equations with only an approximate solution

I have a system of linear equations that is derived partially from experimental data. Theoretically, the system should have a single, exact solution; however, experimental error causes it to not have ...
user avatar
3 votes
0 answers
155 views

Reference Request: Variational Problem

I want to solve approximately the following variational problem: Given a function $c:[-1,1]^2\rightarrow [0,1]$, constants $p_1...p_n\in \mathbb{R}^+$, $\alpha_1...\alpha_n\in \mathbb{R}$, and $\...
user avatar
  • 131
3 votes
1 answer
489 views

Efficient Implementation of Taylor Series for Sine

I am trying out a few forms of polynomial expression optimization, and I'd like to improve of what I've got, if anyone has anything they know is better. Implementation 1: $$x-\frac{x^3}{3!}+\frac{x^...
user avatar
  • 311