Where to correct an inefficiency of algorithm in a published paper? I spotted a serious inefficiency in our algorithm, which was already published. Basically, we have an algorithm to encode a problem A into a formula X. But we later found that we can encode into a formula X', which is equisatisfiable, but with much less (up to thousand) of variables.

This change is very trivial in logic, if we need to correct the algorithm, we only need to change 1 line with one subscript. But it improve the performance drastically, up to 10 times in some instances. 

If somebody build on our work, I don't want them to make the same mistake. If somebody want to compare with our work, I want them to compare with the improved algorithm, not the result we reported in the paper.

But the change is so trivial, how could I let everybody know?
The change only appears trivial to you now that you know about it.

Moreover, while the change may be simple, the validation of that change is not: I'm sure there's lots of experiments to run to verify your statement, and maybe some new analyses to be performed as well.

To me, this sounds like a fine opportunity for a followup.  If your paper was published in a conference, then the improved version can go into the "extended version" journal paper.  If your paper was already published in a journal, this is a good time to follow up with a short conference paper.  If you're in a field that doesn't like conferences, there will probably be journals that take "short papers" or "application notes" or some similar.  

Bottom line: one way or another, there should be a good place to put this not-as-trivial-as-you-think piece of work.