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
1answer
420 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,...
0
votes
2answers
3k views

Successive over-relaxation not converging (when not done in-place)

I'm trying to find the potential given some boundary conditions using the successive over-relaxation method. I have 2 solutions: -One iterates over all elements and applies the formula ...
1
vote
0answers
49 views

A better way to compute a double integral involving a infinite series?

Let $D_{\nu}(.)$ is the parabolic cylinder function (http://mathworld.wolfram.com/ParabolicCylinderFunction.html) And $\Gamma(.)$ is the Gamma function. Define $s_y(\mu,\nu,t,z)=2^{\nu}\...
0
votes
2answers
118 views

Looking for a particular algorithm for numerical integration

Consider the following differential equation \begin{equation} p(t) = \frac{\partial q(t)}{\partial t} \end{equation} where $t \in (0,\infty)$. I have a build a code that spits out values of the ...
-1
votes
1answer
401 views

Finite Difference for Fourth-Order PDE

How to discretize the following 4th order PDE using finite difference method? $$\frac{\partial^{2} y}{\partial t^{2}}+\frac{\partial^{4} y}{\partial x^{4}}=0$$ thanks
2
votes
0answers
92 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 ...
1
vote
1answer
122 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 ...
1
vote
0answers
68 views

Piecewise linear fitting of a curve in loglog plot

Iam basically trying to fit a curve similar to that shown in fig (a) with 7 straight line segments (ie. 6 knots) as shown in fig (b) and I need to get the optimum knot positions. This is a tripartite ...
0
votes
0answers
65 views

approximation of nonlinear time-dependent system with history

I have two time-dependent coupled equations. One of which is several orders of magnitude more computationally demanding than the other. I am trying to use machine learning to reproduce the behavior of ...
5
votes
2answers
444 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}^{...
3
votes
1answer
349 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 ...
1
vote
1answer
214 views

What is the algorithm that matlab used in its built-in function 'pca'?

Do anyone know what is the algorithm that MATLAB used in its built-in function "pca"? I have the following data set: 148.9820 55.8438 210.2150 149.3030 56.8891 208.4280 151.4400 55....
2
votes
0answers
97 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
1answer
2k views

Effect of Initial guess B (approximate Hessian) on BFGS algorithm

I am trying to implement BFGS. The purpose is to approximate Hessian matrix only (not using the quasi-newton optimization steps), so i am using steepest ascent for optimization. What I observe is that ...
8
votes
1answer
188 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 ...
4
votes
1answer
164 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 ...
2
votes
1answer
133 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\...
1
vote
0answers
129 views

Quadratic programming problem involving permutation matrices

Does anyone know a good algorithm for quickly finding an approximate solution to the following problem? Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation ...
11
votes
1answer
945 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)$ ...
1
vote
1answer
72 views

Determine low-order polynomial lower bound

I have a function $f$ I'd like to determine numerically and I have a bunch of $(x, y)$ pairs which approximate the function in the following sense: all of the points satisfy $f(x) \leq y$, most of the ...
1
vote
1answer
1k views

Assigning Groups Based on Preference List [closed]

I am trying to make a system that will sort a list individuals and their preferred list of others. This may not make complete sense, but bear with me. I have a list of people, each with their list of ...
2
votes
0answers
192 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, ...
6
votes
1answer
321 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}+\...
3
votes
2answers
929 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: ...
2
votes
2answers
84 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 ...
7
votes
1answer
789 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 < ...
3
votes
2answers
226 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 ...
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 ...
0
votes
1answer
283 views

Quickly computing inversion of a large sparse partial stochastic matrix

Suppose I have a sparse stochastic matrix $M$ (with thousands or millions of stochastic column vectors), possibly encoding some links in a web graph. Now I split it into two matrices: $D$ containing ...
3
votes
1answer
274 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 ...
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 ...
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 ...
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 ...

1
2