20
$n \log\log n$ is between $n$ and $n \log n$, and is a relatively common one to find in the wild.
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
You're right -- it has absolutely no practical relevance for computing. Even if computing the determinant was an $O(n)$ operation, the complexity of the method would be at least $O(n^3)$ and, consequently, of the same complexity as Gaussian elimination. In practice, computing the determinant of a matrix is actually of exponential complexity, making this ...
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 ...
11
The cost of standard operations like find-and-replace, maxtrix-matrix multiplications and elementwise matrix-matrix multiplications is well-known: Check out the corresponding wiki site.
If you'd really like to know what your MATLAB installation does, you can always go ahead and measure the time, e.g.,
t = zeros(1,100);
for n = 1:100
A = rand(n,n);
...
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
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 ...
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
Matlab 6 used to have a function flop to count them, but it was removed in later versions. The main reason was technical (they switched to LAPACK as the linear algebra core, and it did not return a flop count).
Today this option isn't available anymore; there is no easy equivalent, so if you wish to have one you'll have to count them yourself using the ...
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
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$ ...
7
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 ...
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
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 ...
6
I had to do this once, and the trick is to use the singular value decomposition (SVD). The SVD of $A$ is $A=U\Sigma V^H$, so
$$ \operatorname{tr}(A^{-1}B) \cdot \det A = \operatorname{tr}(V\Sigma^{-1}U^H B) \det \Sigma \det (UV^H)$$
Applying the cyclic permutation invariance of the trace,
$$ = \operatorname{tr}(\Sigma^{-1}U^H B V) \det (\Sigma)\det (UV^H)...
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
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
On a sphere, you can use the nearest neighbor list from the Euclidean distance to get the correct points ordered by distance, because the Euclidean distance is less or equal to the geodesic distance. Once you have that list of points you can simply calculate the geodesic distance for the point of interest. So the fast k-nearest neighbor algorithms based on ...
4
Writing $O(m)+O(n)$ avoids the problem of having to address units. Note that $\max(m,n)$ and $m+n$ have the same order, and having max in a Landau symbol is quite uncommon.
Only top voted, non community-wiki answers of a minimum length are eligible
