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
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
28 votes
6 answers
6k views

How can the gravitational n-body problem be solved in parallel?

How can the gravitational n-body problem be solved numerically in parallel? Is precision-complexity tradeoff possible? How does precision influence the quality of the model?
Sklavit's user avatar
  • 383
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
16 votes
1 answer
1k views

Complexity of MD simulations

I'm new to molecular dynamics (MD) simulations. What is the complexity of a molecular dynamics simulation in terms of simulation time? In other words, if I want increase the simulated time from 10 ...
Daniel Standage's user avatar
14 votes
3 answers
660 views

Scientific Programming Contests

I regularly compete in so called "Programming Contests", where you solve difficult algorithmic problems with your own code and problem solving skills during a limited time-frame. For referential ...
MonadBoy's user avatar
  • 243
13 votes
3 answers
5k views

Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system

I am wondering if the Thomas algorithm is the fastest way (provably?) to solve a symmetric diagonally dominate sparse tridiagonal system in terms of algorithmic complexity (not looking for ...
James's user avatar
  • 1,909
13 votes
2 answers
2k views

Does the "cofactor technique" for inverting a matrix have any practical significance?

The title is the question. This technique involves using the "matrix of cofactors", or "adjugate matrix", and gives explicit formulae for the components of the inverse of a square matrix. It is not ...
Stefan Smith's user avatar
13 votes
4 answers
8k views

FLOP counting for library functions

When evaluating the number of FLOPs in a simple function, one can often just go down the expression tallying basic arithmetic operators. However, in the case of mathematical statements involving even ...
Peter Brune's user avatar
  • 1,675
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
10 votes
3 answers
871 views

Is there a complexity between $O(n)$ and $O(n \log n)$ [closed]

Is there a complexity degree that is bigger than $O(n)$ and smaller than $O(n \log n)$?
user3696586's user avatar
10 votes
2 answers
9k views

Integer operations vs floating point operations

I have been working with an algorithm, which uses additions of floating point vectors, (sparse matrix of floats)x(dense vector of floats) dot products I recently found out that I can get the same ...
Dionysios Georgiadis's user avatar
9 votes
2 answers
338 views

Computation Effort of Algorithms

Consider the strictly convex unconstrained optimization problem $\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$ Let $x_\text{opt}$ denote its unique minima and $x_0$ be a given initial approximation ...
Suresh's user avatar
  • 191
9 votes
1 answer
1k views

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

In Python / Matlab, if you run a routine for SVD on a significantly non-square matrix, X, such as X.shape = (2,15000) you will ...
tisPrimeTime's user avatar
9 votes
1 answer
1k views

N-body simulation optimisation, looking for name or existing work

during the development of my N-body simulation with visualisation in WebGL, I devised an optimisation, and I'm wondering if it has a name. I find it unlikely that it has never been done before. It ...
Magnus Wolffelt's user avatar
8 votes
2 answers
7k views

Why are log and exp considered 'expensive' computations in ML?

In many resources/videos I see comments being made along the lines of "and we can see here that we have a logarithm/exponential so this will be an expensive computation to make." (such as ...
DChaps's user avatar
  • 183
8 votes
5 answers
29k views

Computational Complexity of 2D Convolution

I am using image filtering for an image processing algorithm I'm developing. I'm using a predefined Matlab function to do the convolution, but I'd like to know what the computational complexity is for ...
jake's user avatar
  • 293
8 votes
2 answers
1k views

How does a Sparse Direct Solver know about dimensionality of a problem being solved?

It is claimed that the time and memory complexities of sparse direct solver are $O(N^2)$ and $O(N^{4/3})$ for 3D problems and $O(N^{1.5})$ and $O(N \log N)$ for 2D, respectively. But how does a ...
Alexander's user avatar
  • 1,111
8 votes
1 answer
257 views

Are there improved method of computing the following expression?

given a symmetric matrix $Y \in \mathbb{R}^{n \times n}$, and an arbitrary matrix $X \in \mathbb{R}^{n \times n}$, and a vector $v \in \mathbb{R}^{n \times 1}$, is it possible to compute the following ...
John Smith'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
7 votes
1 answer
362 views

How does the number of function calls in BFGS scale with the dimensionality of space?

Question Is there any estimate for the scaling of the number of function calls in BFGS-optimization with the dimensionality of the search space? Specifically I am assuming a (free) expression for the ...
Kvothe's user avatar
  • 183
6 votes
2 answers
259 views

What are the numerical methods for huge polynomial systems?

Let a system of $n$ polynomial equations of degree $d$ with $m$ variables. I'm interested in a sparse system with $d = 3$, $n \sim 2000000$, $m \sim 50000$ and integer coefficients. What techniques ...
Sebastien Palcoux's user avatar
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
6 votes
1 answer
714 views

Poisson solver on unstructured mesh

For the 2D Poisson equation, there exist on finite-difference mesh, some code taking $O(n \log(n))$ operations to solve it on a mesh with $n$ nodes. They rely on Fast Fourier Transform or Block Cyclic ...
Mathieu Dutour Sikiric's user avatar
6 votes
1 answer
249 views

Efficient algorithm for a matrix product

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
Wolfy's user avatar
  • 295
6 votes
1 answer
118 views

Measures of parsimony for numerical models?

There are hundreds of different types of performance measures for numerical models, many of which are applicable to many different types of models. But a good model doesn't just perform well, it ...
naught101's user avatar
  • 373
5 votes
3 answers
2k views

Computational cost of numerical methods for PDEs

Say I need to solve a PDE numerically. Depending on the problem and the numerical method chosen, I can usually see some issues coming: implementation issues (e.g. boundary conditions, parallelization),...
gnzlbg's user avatar
  • 1,075
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
5 votes
1 answer
353 views

Complexity of recovering all roots of a polynomial

Given a polynomial of degree n and a list of putative roots $\{r_i\}_{i=1}^{n}$, we can verify that all the putative roots are indeed correct by $n$ applications of Horner's method. Hence verifying ...
user14717's user avatar
  • 2,155
5 votes
1 answer
63 views

correct complexity notation

I have written an algorithm where the 2 input arguments are a file and a list of values. I would like to say the algorithm complexity is: ...
Yaron Naveh's user avatar
5 votes
1 answer
228 views

Is there an efficient algorithm for calculation of continued fraction expansion from decimal digits?

Suppose to calculate the continued fraction expansion of $\pi$, the common-sense algorithm would be to take the decimal part, perform inversion, which will give the next term as integer part, and the ...
Syed Fahad's user avatar
5 votes
2 answers
232 views

Restrict Voronoï diagram to a polygon

I managed to build the Voronoï diagram of n points using Fortune's algorithm. This gives me a set of half-edges, some of which being infinite (no starting point and/or no end point). I'd like to ...
Weier's user avatar
  • 151
5 votes
0 answers
540 views

Optimisation of matrix exponential

I have a 7000x7000 sparse matrix (scipy), which I want to exponentiate. I've tried using scipy.sparse.linalg.expm, which works quite well for smaller matrices (takes a few seconds for a 1000x1000 ...
ferros's user avatar
  • 51
5 votes
0 answers
2k views

Two-chordless cycle extraction from a failed comparability graph recognition

I have implemented a comparability graph recognition algorithm from M.C. Golumbic's "Algorithmic graph theory and perfect graphs" book. It is hinted in Fekete, Schepers, and van der Veen's "Exact ...
Gareth A. Lloyd's user avatar
5 votes
1 answer
155 views

complexity constants in median computations same as that of general quantiles?

I would like to know whether the constant in the time complexity of computing the median is different from that of computing general quantiles. In R for example: ...
user189035's user avatar
4 votes
2 answers
557 views

Why is computational cost measured in Floating Pt. Ops. in times of parallel computing?

In times of parallel computing, it seems to me that algorithms (also basic ones, like matrix-vector multiplication) should be measured by their dependent steps (that use results from steps before) ...
Bananach's user avatar
  • 799
4 votes
1 answer
133 views

simplifying a product of a determinant and an inverse of a (nearly) singular matrix

Given two square matrices, $A$ and $B$, I need to calculate the product $tr(A^{-1}B)\times detA$. The catch is that $A$ is singular --- more precisely, it depends on some parameter $t$, such that it's ...
ev-br's user avatar
  • 143
4 votes
1 answer
107 views

Algorithm about finding a combination that the sum is closest to a given number

Given a matrix $P\in \mathbb{R}^{n*k}$ (just for ease of notation, no matrix or linear algebra is actually needed; bound to $(0,1)$ if necessary), select one number from each row and compute the sum. ...
obfish's user avatar
  • 141
4 votes
1 answer
91 views

Worst Case complexity of a search engine algorithm

Computer make it possible to find information in large databases. However, the results are often too large to be returned in their entirety to the user who requests them. Computer therefore sort the ...
user avatar
3 votes
3 answers
8k views

What is the Complexity of MATLAB operations

I'm trying to analyze the complexity of MATLAB code I wrote. I'm trying to figure out how much (in terms of $O$ or $\Theta$) to give functions like find, matrix <...
JNF's user avatar
  • 133
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
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
1 answer
203 views

Big Theta Complexity of Gaussian Elimination using Complete Pivoting

I already know the Big O for partial pivoting is $O(n^3)$ and remain the same for complete pivoting. I also know the big theta complexity for partial pivoting is $2/3 n^3$ I would like to know the ...
Bramanta's user avatar
3 votes
1 answer
197 views

Examples of high polynomial order complexity

I was reading Twenty Questions for Donald Knuth and was intrigued by Knuth's argument in question 17 for why he suspects P=NP. In the discussion he asks why you couldn't have an algorithm bounded by a ...
Rick's user avatar
  • 133
3 votes
1 answer
3k views

Computational complexity of Newton's method

the classical Newton's method for non-linear systems of equations is $x_{k+1} =x_k-J_F(x_n)^{-1} F(x_n)$. In pratice, rather than compute the inverse of the Jacobian matrix, one solves the systems $...
VoB's user avatar
  • 550
3 votes
1 answer
3k views

Time complexity of $l_2$-norm of a vector

What is the complexity (in flops, floating-point operations) of taking the $l_2$-norm of vector $\mathbf{v}\in\mathbb{R}^n$ (or $\mathbf{v}\in\mathbb{C}^n$ if a difference exists). We have the ...
Learn_and_Share's user avatar
3 votes
1 answer
225 views

What is the worst case complexity of the symmetric tridiagonal QR eigenvalue algorithm?

Ignoring eigenvectors, the shifted QR algorithm for computing eigenvalues in the symmetric tridiagional case costs $O(n)$ per iteration, converges globally, and converges cubically near the end. What ...
Geoffrey Irving'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
3 votes
1 answer
101 views

Improve optimization over 'mapping' of indices

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like to associate the rows in the reference ...
kiriloff's user avatar
  • 343
3 votes
2 answers
402 views

How to prove that my problem is np-hard

For an assignment i need to program an application to schedule conversations. Something similar to speeddating or Pta meeting. The problem is that i know that this is hard to solve, but i dont know if ...
Nico Liu's user avatar
  • 131
3 votes
0 answers
145 views

What is the computational cost of using complex numbers in contrast to real numbers in matrix operations, e.g. $LU$ or $LDL^T$ factorizations? [duplicate]

I am curious about how much one loses in terms of computational cost when complex numbers are used instead of real numbers? I guess the number of floating-point operations and memory doubles, but I ...
Armut's user avatar
  • 245