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.
101
questions
1
vote
1
answer
104
views
in Finite Element, which approximation requires less number of unknowns: B-splines vs Shape functions vs Spectral Elements
In Finite Element Analysis, one requires to approximate the solution in terms of basis functions. My questions is, which method in general is better? by 'better', I mean which involves less number of ...
5
votes
1
answer
203
views
How to optimize an approximated matrix multiplication?
[UPDATING]
The old one is a simplified version of the current one. Here is a solution based on the answer proposed by professor Bangerth down below. To describe what I am trying to do, first rewrite ...
- 55
12
votes
2
answers
933
views
Faster Logistic Function
I've noticed that a fairly significant number of cycles in one of my programs are being consumed by the logistic function:
$$f(x)=\frac{1}{1+e^{-x}}$$
Is there a good approximation I can use to reduce ...
- 3,891
1
vote
1
answer
170
views
Kolmogorov n-width
Could someone please point me to an understandable definition of the Kolmogorov n-width? I'm having a hard time figuring out what is the output of the definition - is it an integer?
Edit: I realize ...
- 623
1
vote
1
answer
240
views
Finding the parameters of a function via curve fit
I'm trying to estimate the parameters (v, n, k) defined in fit_func. I tried the default least squares fit but I couldn't find the parameters successfully.
...
- 491
0
votes
0
answers
368
views
Curve fitting using a piecewise polynomial
I am trying to fit a piecewise polynomial function
Code:
...
- 491
1
vote
0
answers
41
views
Integral from function approximations
I have some data which I cannot manage to model and fit with a known function, so let’s say that they are a sample from the unknow function $f(x)$, which look a sort of skewed bell-shaped distribution....
- 111
2
votes
0
answers
56
views
Estimating $n$ column norms of $A$ by using less than $n$ calls to $Ax$?
Suppose I have an $m \times n$ matrix $A$ that is only accessible through matrix-vector products $Ax$. These are expensive, is there a way to approximate vector $x$ of $n$ column norms of $A$ by using ...
- 2,049
3
votes
1
answer
82
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(\...
- 826
9
votes
2
answers
391
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 \...
- 2,049
6
votes
1
answer
210
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\...
- 163
1
vote
0
answers
129
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 $...
- 111
1
vote
0
answers
58
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.
...
- 1,331
1
vote
1
answer
191
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 ...
- 27
0
votes
0
answers
133
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 ...
- 1
5
votes
1
answer
355
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 ...
- 299
3
votes
1
answer
77
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 ...
- 81
4
votes
0
answers
62
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 ...
- 141
1
vote
0
answers
88
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 ...
- 181
3
votes
1
answer
107
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)~~~~~~(...
- 181
1
vote
1
answer
74
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 ...
- 331
3
votes
0
answers
188
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 ...
- 181
3
votes
3
answers
562
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 ...
- 131
2
votes
1
answer
2k
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?
2
votes
0
answers
33
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 ...
- 21
0
votes
2
answers
316
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 ...
- 109
5
votes
1
answer
97
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 ...
- 3,108
4
votes
0
answers
93
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 ...
- 141
4
votes
0
answers
244
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 - ...
- 73
8
votes
1
answer
317
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 ...
- 53.7k
0
votes
1
answer
46
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{\...
- 163
8
votes
1
answer
455
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 ...
- 1,016
2
votes
0
answers
70
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 ...
- 251
1
vote
1
answer
185
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 ...
3
votes
2
answers
297
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 ...
- 131
4
votes
1
answer
190
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 ...
- 985
0
votes
1
answer
92
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}
...
- 109
0
votes
1
answer
283
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 ...
- 225
0
votes
1
answer
113
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(...
0
votes
1
answer
3k
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 ...
1
vote
0
answers
68
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 ...
- 183
0
votes
1
answer
305
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\...
- 245
4
votes
0
answers
90
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 ...
- 985
4
votes
1
answer
948
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\, \...
- 161
4
votes
1
answer
241
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, ...
- 155
1
vote
0
answers
38
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 ...
- 11
1
vote
1
answer
62
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 ...
- 393
5
votes
1
answer
452
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 ...
- 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}
$$
...
- 153
1
vote
0
answers
50
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 ...
- 11