Skip to main content

Questions tagged [complexity]

Relating to the level of difficulty of a calculation or the asymptotic running time of an algorithm.

Filter by
Sorted by
Tagged with
23 votes
3 answers
3k views

Can diagonal plus fixed symmetric linear systems be solved in quadratic time after precomputation?

Is there an $O(n^3+n^2 k)$ method to solve $k$ linear systems of the form $(D_i + A) x_i = b_i$ where $A$ is a fixed SPD matrix and $D_i$ are positive diagonal matrices? For example, if each $D_i$ is ...
Geoffrey Irving's user avatar
48 votes
7 answers
6k views

Is algorithmic analysis by flop-counting obsolete?

In my numerical analysis courses, I learned to analyze the efficiency of algorithms by counting the number of floating-point operations (flops) they require, relative to the size of the problem. For ...
David Ketcheson's user avatar
7 votes
2 answers
556 views

What heuristics can be used to minimize the asymptotic matrix bandwidth of a 5-point Laplacian discretization?

I can see that there are multiple heuristics to achieve a matrix with minimum bandwidth. As heuristics, they can't guarantee an optimal solution in polynomial time (after all, the problem is NP-...
Paul's user avatar
  • 12k
11 votes
2 answers
7k views

How does the computational cost of an mpi_allgather operation compare with a gather/scatter operation?

I'm working on a problem that can be parallelized by using a single mpi_allgather operation or one mpi_scatter and one mpi_gather operation. These operations are called within a while loop, so they ...
Paul's user avatar
  • 12k
6 votes
2 answers
4k views

Fast algorithms to find the eigenvalues of some matrix on intervals of interest

I am curious how to quickly compute the eigenvalues for arbitrary matrices, sparse or dense, restricted on some given interval of interest. Suppose we have an arbitrary $n\times n$ matrix $A$, ...
Shuhao Cao's user avatar
  • 2,552
5 votes
1 answer
4k views

Comparing Algorithmic complexity, ODE Solvers (Big O)

I am currently using the following three methods to solve differential equations: 4th order Runge Kutta Method Euler Method Internal scipy methods: ...
George's user avatar
  • 153
3 votes
1 answer
437 views

Implementation of a $O(n \log(n))$ method to compute eigenvalues of real symmetric tridiagonal matrices

I just came upon this paper, which details the implementation of a fast method to get eigenvalues of tridiagonal symmetric matrices : Coakley, Ed S.; Rokhlin, Vladimir, A fast divide-and-conquer ...
Clej's user avatar
  • 153
3 votes
2 answers
2k views

GPU vs CPU calculation

I've been working on calculating large factorials ($N>10^9$) and I was wondering if it wasn't faster to use the GPU to run the calculations on something like openCL. What I realized however was ...
Bernardo Meurer's user avatar
3 votes
1 answer
3k views

Fast nearest neighbor search, Latitude Longitude

Is there a fast nearest neighbor search algorithm that generates the nearest neighbors, not based on Euclidean distances but based on geographic distances over a set of latitudes/longitudes. The fast ...
hearse's user avatar
  • 259