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
First, the exact answer depends on: (1) usage, i.e. function input arguments, (2) MPI implementation quality and details, and (3) the hardware you're using. Often, (2) and (3) are related, such as when the hardware vendor optimizes MPI for their network.
In general, fusing MPI collectives is better for smaller messages, since start-up costs can be ...
9
You are asking for something overly ambitious if you hope to be able to reliably get within a constant factor (e.g. a couple orders of magnitude) of an optimal method, even just on one type of computer. If someone claimed to have a business analysis technique that could tell you the value of any company in five years, they would be accused of selling snake ...
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
A sparse direct solver knows the matrix, and hence its dimensions and its sparsity pattern. Of course it doesn't know the dimension of the problem dimension before discretization.
However, the sparsity patttern reveals the dimension indirectly. In particular, the complexity estimates you report are based on the assumption that you have a sufficiently fine ...
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
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
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
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
A first order Taylor expansion can be used to improve convergence over simple lagging. Suppose we have a preconditioner (or factors for a direct solve) available for $A+D$, and we want to use it for preconditioning $A$. We can compute
$$\begin{align}
A^{-1} &= (A+D-D)^{-1} (A+D) (A+D)^{-1} \\
&= [(A+D)^{-1} (A+D-D)]^{-1} (A+D)^{-1} \\
...
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 \...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
