Is a faster implementation of an existing algorithm publishable?

Question

So a paper exists, it was published 3 years ago and had a novel algorithm (more or less, it's in the area of finite-difference time-domain simulations).

I've taken the algorithm and accelerated it by a factor of 100x (example, I don't have the true number), producing the same results in the end, but providing an opportunity to essentially simulate more (iterations/objects) in the same amount of time.

The methods used to accelerate it aren't particularly novel, though some aspects might very well be a bit different from mainstream ideas. All in all, a person set out to do the same thing would probably be able to do it, but I would not call it trivial. However, I know that this has not been done before.

Is this something worth publishing? I am going to ask my supervisor, but he's been very busy lately ( >.< ), I haven't been able to catch him for ~4 days. I would like some of your opinions.

Answer 1

If I understand the question correctly, the dilemma is whether to just distribute the code or whether to also make a scientific publication out of it. The way that I typically think about this type of problem is to see whether it passes any of the following tests:

1. Does the improvement enable a significant scientific or technical work that was not previously possible? For example, if faster simulation allows a control loop to be done in realtime that couldn't before, that advance may be scientifically valuable even if the methods are not interesting in and of themselves, but you have to demonstrate that value.

2. Does the improvement make a qualitative change in the operation of the algorithm which is interesting, e.g., changing a scaling property that was previously a limit?

3. Is the mechanism of the improvement interesting in and of itself, e.g., such that it teaching something about the nature of the algorithm or such that it might be applied to other algorithms or problems as well?

Any of these is a good reason to publish an improvement on an algorithm.

Answer 2

@jakebeal answer is spot-on, but I will add my extra two cents. As you said you parallelized the algorithm, which is good but how did this happen?

• Was the algorithm already parallel and just has not been implemented that way? If yes, simply parallelizing the implementation might not be good enough.

• Did you used other additional optimizations to make it efficient? For example did you use SIMD (SSE, AVX) instructions or GPUs for your implementation?

• As jakebeal said, did you alter the scope of the algorithm? If the algorithm could handle e.g. only small graphs up to a size, with your implementation it might scale to much larger graphs.

• If, for example you worked on an indexing method, did your method improved the building of the index or also improved the index's query performance?

The most important thing to consider, is that you need to write a full paper to present your improved version. So, if all you can say is "I parallelized the algorithm with OpenMP and is now faster" or "I vectorized this loop" and other technical details, this will not be good enough for a scientific paper. On the other hand, if you worked on advanced techniques (SIMD, GPUs), your work might worth a publication. Still, it might not be good enough for top-algorithm conferences (where new algorithms are usually presented) and might be more suitable for conferences focused in parallel algorithms, implementations, which are more focused on the technical side of things. Also, I would worry about the fact that no one touched this algorithm for 3 years. Are you sure there is not another algorithm that is now the state-of-the-art for this particular problem? You should look into this too.

Update: Since you already have a done a GPU-CUDA version of this algorithm, it would be interesting to actually extend your work on plain multicores with a) OpenMP (that would be trivial) b) OpenMP + SIMD (that would be harder c) or OpenMP + SIMD + partial CUDA. Having several tuned versions of the same algorithm for different architectures and performance benchmarks for the different versions, would make a much stronger paper.

Answer 3

One option that you have is to submit a paper to a demo session of a conference. Such papers usually describe existing systems so they don't have to be new. If you are accepted, your paper is published in the proceedings, and you have the right to present a live demo of your system in the conference. If your improved implementation indeed makes 3D possible, you may have a very impressive demo.

Answer 4

How is your code faster than the state of the art? If it's faster only because you're a good programmer, you're unlikely to be able to publish in a worthwhile venue. If it's faster because you did some computer science, you might be onto something.

Answer 5

I have also published some papers in the same vein. If you can find something novel about your implementation (significant changes to the algorithm, novel optimizations, new insights about the architecture, etc.) then you have a better chance of getting published. If you only achieved the speedup by parallelizing the algorithm in a straightforward fashion, it will stand less of a chance at the higher tier conferences. 5 or 6 years ago when GPGPU programming was still very new, people were often publishing papers about GPU parallelized algorithms. This is becoming less frequent now, because many of the fundamental concepts about this process have already been explored. Much of the low hanging fruit in that area has been picked, so reviewers will tend to view straightforward parallelization of algorithm "X" as not very novel.

Answer 6

I'd say simply write a paper, submit it at one of the top venues in that area and let the reviewers decide for you. If it was rejected they will suggest the changes that could get it accepted in the following conference.