Method for modifying frequency-domain signal to produce predetermined time-domain signal We are performing a convolution of audio signal, with 511th order FIR
filters, using fast convolution methods: overlap-add or overlap-save.
Filters are being designed in frequency domain several thousand times
per second. Filters need to be zeros padded to be used in order to be
used in fast convolution algorithms, so to acquire appropriately
padded filters we do:


frequency domain filter design, filters of 511th order
IFFT into time domain
zeros padding to 2048 length (1536 zeros)
FFT back into frequency domain (for multiplication with spectral
representation of input audio signal)


Computational complexity of such operation occurred be to high for our
needs. We're trying to figure out if there's a method to avoid
IFFF->FFT steps and reduce the overall complexity from O(NlogN) to
O(N). Any ideas if it is possible, and, if so, how can it be achieved?
Zero-padding is one domain is equivalent to Sinc (or Dirichlet) convolution in the other, which is O(n^2), so that won't save you.  For less computation, you might want to try different filter design methods (compositing existing FIR filters, IIRs, etc.) or finding a way to recompute your filter less often.