20
$n \log\log n$ is between $n$ and $n \log n$, and is a relatively common one to find in the wild.
19
To add to Lutz Lehmann's answer, you can look up the latency for the CPU instructions in this comprehensive table by Agner Fog.
For example, on the Intel Ivy Bridge processors:
FADD / FSUB (floating point add and subtract) both take 3 cycles
FMUL (multiply) takes 5 cycles
FDIV (divide) takes 10-24 cycles
FYL2X ($y \cdot \log_2(x)$) takes 90-106 cycles
F2XM1 ...
14
It's typically very hard if not impossible to implement a parallel version of an iterative algorithm that paralellizes across iterations. The completion of one iteration is a natural sequence point. If one algorithm requires fewer iterations but more work per iteration, then it's more likely that this algorithm can be effectively implemented in parallel.
...
12
I believe comparing an iterative method (multigrid) to a direct/exact method (Thomas) in terms of exact operation count isn't really meaningful. IIRC, Thomas operation count is $8N$ for any tridiagonal system. The only time I can imagine multigrid conceivably beating that is for a trivial case of having a linear solution, and even then the cost of evaluating ...
12
I don't know of any current contests, but you can definitely have a look at the SIAM 100-digit challenge. It's a set of 10 problems for which the contest required 10 correct digits per problem. All problems are of the type "if you do it blindly, you'll only get a couple of digits" (unless you resorted to multi-precision arithmetic with in some cases a huge ...
12
odeint from the SciPy library defaults to the lsoda integrator described here. However, any simple description of asymptotic computation time is impossible. The reason is many fold.
First, let me describe the algorithm. A common multistep algorithm for non-stiff equations are the Adams-Moulton methods. While these are implicit, the Adams-Bashforth methods ...
11
The short answer is that the Thomas algorithm will be faster than any iterative scheme for almost all cases. The exception would perhaps be applying a single iteration of a very simple iterative scheme such as Gauss-Seidel, but this is highly unlikely to give an acceptable solution. Also, this is ignoring parallel processing concerns.
Multigrid is an ...
11
$\exp$, $\sin$, $\tan$ and their inverse and otherwise related functions are transcendental, defined by an infinite power series. Meaning it takes some effort to evaluate uniformly good approximations. This is done via argument simplification using the properties of these functions, and polynomial approximations, or using quotients of polynomials à la Padé ...
9
I'm going against the crowd - the adjugate matrix is in fact very useful for some specialty applications with small dimensionality (like four or less), in particular when you need the inverse of a matrix but don't care about scale.
Two examples include computation of an inverse homography and Rayleigh quotient iteration for very small problems (which in ...
9
There are a lot of ways to speed up convolution is specialized contexts, e.g.:
If your filter is separable, i.e. $h = h_1 * h_2$ with $h_1\in\mathbb{R}^{n\times 1}$ and $h_2\in\mathbb{R}^{1\times m}$, calculating $(u*h_1)*h_2$ is much faster than $u*(h_1*h_2)$.
Convolving with $h = [1\ \dots\ 1]$ (for any length) can be done recursively with basically two ...
8
In fact, the precise total number of operations is very rarely used as a measure of computational cost. Instead, you will most often see the computational order (i.e. $\mathcal{O}(n^3)$). This "big O" notation roughly means that the number of operations is proportional to $n^3$ and tells you how the total number of operations scales as the number of unknowns ...
8
There is a nice discussion on StackOverflow regarding floating point vs integer operations. In short, the performance of the operations depends a lot on
processor architecture
how the data is stored in memory and in which order it is accessed
if (and which) SSE/AVX/AVX2/etc instructions are used (and how efficiently)
This probably provides some insight ...
8
I think the method has too much implementation complexity and too narrow applicability to be worth it.
Though the paper is correct to point out the importance of solving the tridiagonal-symmetric eigenproblem in the course of solving the general-symmetric eigenproblem, it neglects to mention that the "frontend" procedure between these two scenarios (...
7
On top of $O(n\log(\log(n)))$, there's also $O(n \log^*(n))$ in which $\log^*$ is the number of times the logarithm function must be applied in order for the result to be less than or equal to 1.
For instance, if you already know an Euclidean minimum spanning tree, the Delaunay triangulation may be discovered in $O(n\log^*(n))$ time.
More extremely, one ...
7
A convolution becomes a product if you apply it in Fourier space, so you can express the operation $I * m$ ($I$ being the image, $m$ being the mask with which you filter) as $I * m = F^{-1}(F(I) \cdot F(m))$ (where $F$ is the Fourier transform) which will cost you $O(MN \log (MN))$ operations. Whether this is cheaper than what you have depends on the size of ...
7
I can think of some possibilities:
If both algorithms monotonically reduce the error with each iteration, then it might be preferable to some to have more, cheaper iterations since it gives you more choices about when to stop iterating.
If $\mathcal{A}_1$ is $O(n)$ work and time but $O(n^k)$ memory, you might prefer $\mathcal{A}_2$ if $k$ is large. $k=2$ ...
6
This may have gone unnoticed in the comments under the original question, but computing $10^9!$ yields a number with 8.5 billion digits, that is it is on the order of $10^{9\cdot 10^9}$. Given that $10^{9\cdot 10^9}=1000^{3\cdot 10^9} \approx 1024^{3\cdot 10^9}=(2^{10})^{3\cdot 10^9}=2^{3\cdot 10^{10}}$, you need approximately $3\cdot 10^{10}$ bits, or ...
6
The method you describe is somewhat similar to the Barnes-Hut algorithm. The main difference is that you have a single level of close interactions, whereas the Barnes-Hut has $\log N$.
In the Barnes-Hut, all particles are put into an octree, and the gravitational force computed between the elements every node. Computational complexity then drops to $O(N \...
6
As pointed out in the comments, the cost of evaluating $f$ is critical, and in most practical cases will be the dominant cost. Lets suppose it takes $C$ operations to evaluate $f$. For nontrivial functions, $C$ will be at least $\mathcal{O}(N)$ just from using the $N$ arguments.
Also pointed out in the comments, the finite difference formula you have does ...
5
First of all, a bit on the terminology. FLOPS are "floating point operations per second", and they are typically not used to measure the performance of algorithms, but of machines.
I assume that you mean that the complexity of algorithms is measured in the total number of floating point operations required to do the job (probably one could write that as ...
5
A thread on cstheory has a few examples. So, there are definitely algorithms with very high exponents that were made for purposes other than simply creating a high-polynomial-order algorithm.
However, the tricky bit is that for any high-order algorithm to be useful, $N$ has to be really really small. In physics, I don't know of any high order polynomial ...
5
Certified homotopy continuation methods are used both for finding roots and for proving that they indeed exist (inside a certain interval). A quick web search turned out this paper: Reliable homotopy continuation by Joris van der Hoeven.
5
Response surface models (a kind of surrogate model) are often used in situations like this. The idea is to sample values of the parameters $a$ and $b$, compute $R(a,b)$ at each point, and then build a regression model (typically quadratic or even higher order) of the function. You can then optimize over the the fitted model.
5
The "100,000 unknowns" rule-of-thumb applies to sparse matrices rather than dense ones. A naive direct solver, which doesn't take advantage of sparsity at all, could in principle have $O(n^3)$ complexity for some matrices. In practice, a good direct solver will have much lower computational complexity.
A better starting point would be to look at banded ...
5
Integer operations are generally faster than floating point operations, but the gap is far less than it was, say, 30 years ago when everyone was still counting FLOPS. The difference may be a factor of 3 or 5 now between a fp-fp operation and an integer-integer operation.
But in both cases, at least if your problems become large enough that they don't fit ...
5
It's complicated. It depends on what 'counts 1'.
From the $\frac23n^3$ number you are reporting, I presume you are counting either multiplications or FMAs as your basic operations, which is one of the possible way to count "flops", or floating point operations.
In this case, the pivoting requires zero floating point operations, so it costs zero. The cost ...
4
Not entirely sure this is applicable to your situation, but I think it may be. Statisticians use something called an information criterion for purposes very similar to this. It captures the trade off between good fit of the observations (in particular, the likelihood of the observations given the model and a setting of the parameters) and the complexity of ...
4
I don't think is possible given that the nature of solutions to PDEs varies so much. However, a general heuristic you can have in your head is something like:
Find out what type of equation (Eliptic, Parabolic, Hyperbolic).
Look at the coefficients in the problem / the Jacobian. Is the problem stiff? If so you'll want some kind of implicit method (i.e. ...
4
That heavily depends on the representation.
If you're given $P_1$ and $P_2$ as systems of linear inequalities (or, dually, as the convex hull of a finite set of points) with finite precision, you can reduce each linear system (or finite point set) to an irredundant system of linear inequalities by solving linearly many linear programs. Then scale each ...
4
There are infinitely many, since $O(n(\log n)^\alpha) \subsetneq O(n(\log n)^\beta)$ for any $\alpha<\beta$. So, in particular, $O(n) = O(n(\log n)^0) \subsetneq O(n(\log n)^\alpha) \subsetneq O(n\log n)$ for any $\alpha\in (0,1)$.
Only top voted, non community-wiki answers of a minimum length are eligible