Skip to main content
23 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 ...
Daniel Shapero's user avatar
16 votes
Accepted

Why is it that SVD routines on nearly square matrices run significantly faster than if the matrix was highly non square?

You are asking for a full (dense) SVD, which also needs to generate the unitary components of $U$ and $V$ which correspond with the null space of your input. for the $1000 \times 800$ case, your input ...
helloworld922's user avatar
13 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 ...
Chris Rackauckas's user avatar
11 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 ...
GertVdE's user avatar
  • 6,159
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 ...
Infinity77's 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....
Lutz Lehmann's user avatar
  • 6,109
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 ...
Anton Menshov's user avatar
  • 8,672
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 ...
rchilton1980's user avatar
  • 4,936
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 ...
Steven Roberts's 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 ...
Brian Borchers's 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)$ ...
Daniel Shapero's 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 ...
Wolfgang Bangerth's 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 ...
Federico Poloni's user avatar
4 votes

What is an instance (precisely) in computational complexity?

Pragmatically, an instance just means an input/output pair of an algorithm. I think a better example of a reduction would be transforming multiplication into repeated addition. For example, the ...
rchilton1980's user avatar
  • 4,936
4 votes
Accepted

Time complexity analysis

It's O(n), but it depends on the sorting algorithm you use. Finding unique elements is O(n) with a hash table. You use one for loop to count incidents and a subsequent loop to extract uniques. ...
Richard's user avatar
  • 3,971
4 votes

Asymptotic Complexity of Gaussian Elimination using Complete Pivoting

Carl's answer is correct, I upvoted it too. The growth in pivot searches from taking $O(n^2)$ steps to $O(n^3)$ steps is unfortunate, but doesn't jeopardize the overall complexity. But I think the ...
rchilton1980's user avatar
  • 4,936
4 votes
Accepted

Asymptotic Complexity of Gaussian Elimination using Complete Pivoting

Yes. Searching the entire trailing submatrix for the next pivot instead of only the current column merely replaces the time spent on finding pivots from $O(n^2)$ to $O(n^3)$. While the total runtime ...
Carl Christian's 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 ...
Kirill's user avatar
  • 11.4k
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\...
Anton Menshov's user avatar
  • 8,672
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 ...
Tyler Olsen's user avatar
  • 1,512
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 ...
Juan M. Bello-Rivas's user avatar
4 votes
Accepted

Flops of the computation of symmetric matrix $A$ to the power of $p$

You can do this in $O(n^3)$ floating point operations by diagonalizing the matrix and applying the spectral theorem.
Brian Borchers's user avatar
4 votes
Accepted

Diagonalization of Hermitian matrices vs Unitary matrices

LAPACK doesn't have a specialized routine for computing the eigenvalues of a unitary matrix, so you'd have to use a general-purpose eigenvalue routine for complex non-hermitian matrices. This is ...
Brian Borchers's user avatar
4 votes

Asymptotic complexity of fixed-rank SVD

Yes. You can run rank-revealing QR on your matrix $A$, which will stop at step $k$ (hence effectively terminating in $O(mnk)$) and produce $A = QRP$, where $R$ has nonzeros only in its first $k$ rows, ...
Federico Poloni's user avatar
4 votes
Accepted

Complexity of recovering all roots of a polynomial

Evaluating a polynomial of degree $<n$ in $n$ points can be done in time $O(n\log n)$. This is called fast multipoint evaluation; see for instance von zur Gathen, Modern Computer Algebra, ch. 10.
Federico Poloni's user avatar
4 votes
Accepted

Space complexity of a semidefinite program

For a problem with $m$ linear equality constraints and a $n$ by $n$ matrix variable, the problem data $A$, $b$, $C$ requires $O(mn^{2})$ storage for $A$, $O(m)$ storage for $b$, and $O(n^{2})$ storage ...
Brian Borchers's user avatar
3 votes
Accepted

Notations for algorithmic complexity in elementary operations

The categories you use were meaningful a couple of decades ago when floating point operations were expensive compared to all other kinds of things processors did. But they are no longer: for example, ...
Wolfgang Bangerth's user avatar
3 votes

Scientific Programming Contests

One alternative would be top coder data science competitions. It doe not fit your description, but you can encounter very often contests which are a combination of algorithms - combinatorial - ...
Aurelian Tutuianu's user avatar
3 votes

Convergence rate and complexity for convex minimization problem

Unlike the first two cases on page 36, case 3, "Quadratic rate", has a bound on $r_{k+1}$ that depends on $r_{k}$ rather than $k$. We have $r_{k+1} \le cr_{k}^{2}$ $r_{k+1} \le c(cr_{k-1}^{2})^{2}...
Brian Borchers's user avatar
3 votes

Calculate amount of FLOPs for an eigenvalue problem solver

The solution would be using PAPI (performance API) library http://icl.cs.utk.edu/papi/. There is a Windows and Linux Version. In order to use it on MATLAB or Octave code, you would have to add the ...
Kosha Misa's user avatar

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