19

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 point add and subtract) both take 3 cycles FMUL (multiply) takes 5 cycles FDIV (divide) takes 10-24 cycles FYL2X ($y \cdot \log_2(x)$) takes 90-106 cycles F2XM1 ...


11

$\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. This is done via argument simplification using the properties of these functions, and polynomial approximations, or using quotients of polynomials à la Padé ...


4

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, and $Q,P$ are orthogonal. You can now compute and SVD of $R$, and use it to piece back the factors with a few matrix products with cost $O(\max(m,n)k^2)$.


4

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 slower than using a routine for the eigenvalues of a complex hermitian matrix, although I'm surprised that you're seeing a factor of 20 difference in run times. ...


2

The quantum equivalent of how many bits you need to store is the number of "qubits" are required for a certain computation. The quantum equivalent of the number of operations is the number of "gates" that need to be applied.


2

TL;DR For an image of size $m\times n$ you can solve this problem in $O(nm(\log(n) + \log(m)))$. In fact, there is nothing to "solve", the solution can be written down analytically. The differencing operator is linear space invariant, i.e. a convolution, and you are asking how to do a "de-convolution". This can be done efficiently in the ...


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