Relating to the level of difficulty of a calculation or the asymptotic running time of an algorithm.
1
vote
0answers
17 views
Comparison search algorithm with repeated elements
I am studying the Grover algorithm and I want know what's the computational complexity of the best classical algorithm that finds an element in set $M$ with probability $p\geq 1/2$?. I know for ...
3
votes
3answers
107 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 ...
1
vote
1answer
72 views
How to calculate the complexity of a given Algorithm
I have the following algorithm given:
Input: Regular Matrix $A \in \mathbb R^{n,n}$
Output: LU-Decomposition of A = LU
for k = 1, . . . , n do
for j = k, . . . , n do
$r_{kj} = a_{kj} − ...
3
votes
1answer
54 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 ...
2
votes
2answers
44 views
Clustering Algorithm for a congruence relation?
Say we are given a congruence relation$~\sim$ in a dataset with $n$ elements. I am looking for an algorithm for optimally sorting the $n$ elements into $m$ clusters according to given congruence ...
5
votes
2answers
107 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 ...
2
votes
2answers
78 views
How does an automaton actually “compute”?
In my studies in computability I have come across the notion of the "machine", an abstract representation of a device that essentially computes. I have read about Turing Machines and Wolfram's binary ...
3
votes
1answer
62 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 ...
6
votes
1answer
124 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 ...
2
votes
2answers
213 views
Quadratic program With Linear Constraint vs. Eigen Decomposition Time Complexity-Comparison. Which is faster?
Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be-as in - Is ...
5
votes
1answer
45 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:
...
2
votes
2answers
193 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, ...
3
votes
2answers
119 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 ...
3
votes
1answer
66 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 ...
2
votes
0answers
36 views
Complexity of direct solvers? [duplicate]
Possible Duplicate:
How to reorder variables to produce a banded matrix of minimum bandwidth?
What is the time and space complexity of direct sparse solvers (e.g., UMFPACK, SUPERLU, ...
5
votes
1answer
227 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 ...
6
votes
2answers
388 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 ...
4
votes
2answers
475 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$, ...
5
votes
1answer
106 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:
...
5
votes
0answers
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 ...
7
votes
4answers
742 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 ...
2
votes
2answers
165 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 acheive a matrix with minimum bandwidth. As heuristics, they can't guarantee an optimal solution in polynomial time (after all, the problem is NP ...
1
vote
3answers
387 views
Computational Complexity of Image Segmentation algorithms
I have a question. I need to calculate the computational complexity of image segmentation algorithms. Can anyone please help me?
For example, I have a screen-size picture with white background ...
11
votes
3answers
368 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 ...
16
votes
5answers
665 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?
26
votes
5answers
722 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 ...
10
votes
1answer
166 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 ...
