20
votes
Is there a complexity between $O(n)$ and $O(n \log n)$
$n \log\log n$ is between $n$ and $n \log n$, and is a relatively common one to find in the wild.
- 10.8k
20
votes
Accepted
Why are log and exp considered 'expensive' computations in ML?
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 ...
- 8,142
12
votes
Accepted
Scientific Programming Contests
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 ...
- 6,066
12
votes
Accepted
Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system
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 ...
- 2,203
12
votes
Accepted
Comparing Algorithmic complexity, ODE Solvers (Big O)
odeint from the SciPy library defaults to the lsoda integrator described here. However, any simple description of asymptotic ...
- 11.6k
11
votes
Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system
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 ...
- 4,521
11
votes
Accepted
How does the number of function calls in BFGS scale with the dimensionality of space?
That very much depends on your objective function. If you know that your objective function is highly multi-modal and complex, then BFGS is only going to give you a local minimum. If that is enough ...
- 226
11
votes
Why are log and exp considered 'expensive' computations in ML?
$\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....
- 3,601
9
votes
Does the "cofactor technique" for inverting a matrix have any practical significance?
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 ...
- 161
8
votes
Accepted
GPU vs CPU calculation
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 $...
- 50.7k
8
votes
Accepted
Integer operations vs floating point operations
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 ...
- 8,362
8
votes
Accepted
Implementation of a $O(n \log(n))$ method to compute eigenvalues of real symmetric tridiagonal matrices
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 ...
- 4,316
7
votes
Is there a complexity between $O(n)$ and $O(n \log n)$
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 ...
- 1,645
7
votes
Time complexity of numerical finite differences
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 ...
- 934
6
votes
Accepted
N-body simulation optimisation, looking for name or existing work
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-...
- 2,473
5
votes
Accepted
Examples of high polynomial order complexity
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.
...
- 2,473
5
votes
What are the numerical methods for huge polynomial systems?
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 ...
- 3,954
5
votes
Accepted
What kind of optimisation algorithm is suitable for a computationally expensive function?
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 ...
- 17.6k
5
votes
Regarding impractical usage of direct solvers of linear systems
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)$ ...
- 8,142
5
votes
Integer operations vs floating point operations
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 ...
- 50.7k
5
votes
Accepted
Big Theta Complexity of Gaussian Elimination using Complete Pivoting
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 ...
- 8,730
4
votes
Time complexity for sparse direct solver for SPD system with respect to number of equations, bandwidth, number of nonzeros?
The complexity of direct solver for SPD problems depends essentially of the properties of the underlying graph. If your matrix comes from the discretization of an elliptic equation then it depends ...
- 435
4
votes
What are the numerical methods for huge polynomial systems?
For this kind of large scale problem, using method like Gröbner basis, or other generally used to solve polynomial system, require lots of calculation time and many times your "solution" is so big you ...
- 171
4
votes
difference of polytopes in $\mathbb{R}^n$
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 ...
- 372
4
votes
Is there a complexity between $O(n)$ and $O(n \log n)$
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\...
- 141
4
votes
Computational cost of numerical methods for PDEs
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, ...
- 11.6k
4
votes
Accepted
Efficient algorithm for a matrix product
A key to solving such problems is in the understanding of the definition of a matrix-matrix product. Without loss of generality, for square matrices $A,B\in\mathbb R^{n\times n}$, $C\in \mathbb R^{n\...
- 8,362
4
votes
Accepted
finding the growth rate from numerical data
Plot your data in two different ways:
$\log(y)$ vs $x$
$\log(y)$ vs $\log(x)$
If your data appears to be linear in the first case, then your data takes the form $y(x) = A\cdot c^x$, and the line ...
- 1,522
4
votes
Accepted
Time complexity of $l_2$-norm of a vector
The square root is counted as a single floating point operation in the IEEE 754-2008 standard although that does not mean that it takes the same time as other operations. On Intel Xeon processors, the ...
- 3,954
4
votes
Accepted
Computational complexity of Newton's method
If you take $m$ steps, and update the Jacobian every $t$ steps, the time complexity will be $O(m N^2 + (m/t)N^3)$. So the time taken per step is $O(N^2+N^3/t)$. You're reducing the amount of work you ...
- 11.4k
Only top scored, non community-wiki answers of a minimum length are eligible