The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
17
votes
1answer
3k views

Drawbacks of Newton-Raphson approximation with approximate numerical derivative

Suppose I have some function $f$ and I want to find $x$ such that $f(x)\approx 0$. I might use the Newton-Raphson method. But this requires that I know the derivative function $f'(x)$. An analytic ...
15
votes
4answers
1k views

Can the solution of a linear system of equations be approximated for only the first few variables?

I have a linear system of equations of size mxm, where m is large. However, the variables that I'm interested in are just the first n variables (n is small compared to m). Is there a way I can ...
14
votes
6answers
974 views

Approximate spectrum of a large matrix

I want to compute the spectrum (all the eigenvalues) of a large sparse matrix (hundreds of thousands of rows). This is hard. I am willing to settle for an approximation. Are there approximation ...
14
votes
1answer
3k views

The Remez Algorithm

The Remez algorithm is a well-known iterative routine to approximate a function by a polynomial in the minimax norm. But, as Nick Trefethen [1] says about it: Most of these [implementations] go ...
12
votes
1answer
4k views

Efficient solution of mixed integer linear programs

Many important problems can be expressed as a mixed integer linear program. Unfortunately computing the optimal solution to this class of problems is NP-Complete. Luckily there are approximation ...
11
votes
1answer
844 views

Numerical methods for inverting integral transforms?

I'm trying to numerically invert the following integral transform: $$F(y) = \int_{0}^{\infty} y\exp{\left[-\frac{1}{2}(y^2 + x^2)\right]} I_0\left(xy\right)f(x)\;\mathrm{d}x$$ So for a given $F(y)$ ...
8
votes
1answer
179 views

Efficient Gravitational Field Implementation

I asked a similar question on physics.stackexchange, being ignorant about this website. I am basically looking for an efficient way to implement gravitational fields. I have a huge 2D space, with ...
7
votes
1answer
758 views

Polynomial Fitting from Chebyshev Coefficients

I have been reading Numerical recipes about how to create a power series approximation to a function once you have a Chebyshev approximation to the function. However it is still very unclear to me how ...
7
votes
3answers
1k views

Choosing subset of vectors to approximate a subspace

Suppose I have a high-dimensional vector space $X$, a subspace $V \subset X$, and a collection of $n$ vectors $\{x_i\}_{i=1}^n \subset X$. My question is: How can I choose a small collection $k < ...
7
votes
1answer
211 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 ...
7
votes
2answers
717 views

Bin-packing: Maximise number of bins / “Fukubukuro” problem?

I recently encountered a problem that looks like a variation of bin packing or knapsack problem, but with the objective to maximise the number of bins/knapsacks: Consider there is a list of M items ...
6
votes
1answer
270 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 ...
6
votes
1answer
315 views

Computing $\sin(\pi/2)$ numerically

I'm trying to understand the types of numerical errors, to do this I want to calculate $\sin(\pi/2)=1$ numerically. To do this I use the Taylor series of $\sin(x)$ in 0: $$\sin(x)=x-\frac{x^3}{6}+\...
6
votes
1answer
383 views

Fast algorithm for computing matrix square root using randomized linear algebra?

Is there a fast algorithm for computing the matrix square root of a real symmetric matrix using random matrices or randomized algorithms?
6
votes
3answers
3k views

Fast algorithm for Polar Decomposition

As it known, according to the Polar Decomposition, square matrix can be expressed in the next form $$M=QR$$ ($Q$ - orthogonal matrix $R$ - positive-semidefinite Hermitian matrix) I need to find this ...
6
votes
1answer
363 views

Matching/Assignment Problem

I'm not sure how I can represent and solve the following problem. I have a list of sales (timestamp and quantity) and a list of corresponding inventory draws (timestamp and quantity). What I ...
5
votes
2answers
385 views

Computation of multipole expansion of potential not converging

According to Beatson and Greengard's short course on FMM: ( Eq. 5.15 & 5.16 setting k=1, q=1 ) We can approximate a potential $\phi = 1/(r-R)$ using: $$ {1\over |\vec{r}-\vec{R}|} = \sum_{n=0}^{...
5
votes
1answer
126 views

Using an approximation algorithm to adapt parameter values of a given algorithm

Problem: I have an incremental online clustering algorithm which need 4 parameters that should be specified by the user before execution. The algorithm will gives "good results" if "a good parameter ...
5
votes
1answer
348 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 ...
5
votes
2answers
2k 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 ...
5
votes
0answers
124 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 ...
4
votes
1answer
137 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, ...
4
votes
1answer
54 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 ...
4
votes
1answer
469 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\, \...
4
votes
1answer
238 views

Problems Implementing the Remez Algorithm

So first off: *** This code is not being used in production software. It is a personal project of mine, trying to understand approximation theory and advanced curve fitting. In other words, I'm ...
4
votes
1answer
159 views

Updating an approximate solution to a linear system in response to a small change

This question was original posted on SO but it was suggested that I post it here. I'm working on a program in which I have a banded matrix M and a vector b, and I want to maintain an approximate ...
4
votes
0answers
60 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 ...
4
votes
0answers
80 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 - ...
4
votes
0answers
82 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 ...
3
votes
1answer
404 views

Efficiency of an algorithm

I designed an algorithm to find the global minimum of a function and implemented it in MATLAB. And I also implemented the "Tunneling algorithm" for the global minimum of a function in MATLAB. But now,...
3
votes
2answers
276 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 ...
3
votes
2answers
895 views

How to detect key turning points on a driven road?

I am looking for a description of algorithm which allows me to detect key turning points on the road amongs a set of all given points. I've ilustrated my problem on the below image: Green spots: ...
3
votes
1answer
340 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^...
3
votes
1answer
273 views

Integral average approximation and error bounds

I'm looking into integrals of the form: $$\int_a^b {f(x)g(x)dx}$$ Where $f(x)$ is unknown, but it's integral is: $$\int_a^b {f(x)dx}=F$$ It's been suggested to me that one could approximate this ...
3
votes
2answers
196 views

How to prove that my problem is np-hard

For an assignment i need to program an application to schedule conversations. Something similar to speeddating or Pta meeting. The problem is that i know that this is hard to solve, but i dont know if ...
3
votes
2answers
177 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 ...
3
votes
1answer
330 views

Computing the (non-convex) boundary of a set of paths between two points

I have a set of paths between two fixed points (marked in red below). Each of these paths consists of an ordered series of $\{x, y\}$ points (marked in blue). I am trying to find the ordered set of ...
3
votes
0answers
151 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 $\...
2
votes
2answers
1k 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 ...
2
votes
1answer
88 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 ...
2
votes
2answers
82 views

Estimate (non-)drift in noisy data

I have a time series representing the result of a complex calculation (physical simulation). Due to round-off errors and approximation errors, there will be some "noise" on the data series. In some ...
2
votes
1answer
138 views

Numerically designing a periodic 1D curve that maximizes an integral area objective and satisfies value, derivative, and frequency constraints

I need to write MATLAB program (or use an existing one) to obtain Fourier series coefficients. Let's say the series is going to approximate a 1D curve. The boundary conditions are: value of the ...
2
votes
1answer
130 views

What is the more than 3rd order Taylor series approximation for a multi-variate function?

Suppose $f$ is a infinite continuously differentiable map: $R^n\to R$, and $x,x_0 \in R^n$, then we have the following second order Taylor expansion of $f(x)$ at $x_0$: $$f(x)\approx f(x_0)+(x-x_0)^T\...
2
votes
0answers
148 views

What algorithm does (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 ...
2
votes
0answers
51 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 ...
2
votes
0answers
88 views

Finding most efficient route (distance/number of nodes) that uses nodes at least X amount away from another node

I'm trying to find the "looped" route with the lowest value of D/n, where D=Distance, and ...
2
votes
0answers
89 views

Algorithm for optimizing graph interconnectivity

I have a partiuclar kind of graph problem and (not having a background in graph algorithms) I would like to know how this kind of problem is called in the literature and what algorithms exist for ...
2
votes
0answers
182 views

Good approximate solutions for a MILP problem

The company I work for has been developing an application for real-time control of sewer networks. Every 5 minutes, a MILP problem is built or updated, then solved using Gurobi. For mid-sized cities, ...
1
vote
1answer
1k 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} $$ ...
1
vote
1answer
115 views

What are good parametrizations of rational functions for response surface models?

For fitting a response surface model to a physical process, I have 3-4 relevant "signals", like a feature density, a signal based on a feature width, or a signal based on a distance to the next ...