Where to correct an inefficiency of algorithm in a published paper?
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.