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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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....
user avatar
  • 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 ...
user avatar
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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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-...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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)$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
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, ...
user avatar
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\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 11.4k

Only top scored, non community-wiki answers of a minimum length are eligible