How to elevate the priority of AsyncTask?

Try to use following (increase of priority AsyncTask threads):

protected final MyResult doInBackground(MyInput... myInput) {
    Process.setThreadPriority(THREAD_PRIORITY_BACKGROUND + THREAD_PRIORITY_MORE_FAVORABLE);
    // blah-blah
}

If you do not have a heavy UI which would interleave with the AsyncTask flow of execution, then your problem is in the algorithm used.

If you can divide your algorithm in parallel tasks, then you can use a pool of executors. If not, your Async Task is just doing serial work.

Be aware that according to AsyncTask:

When first introduced, AsyncTasks were executed serially on a single background thread. Starting with DONUT, this was changed to a pool of threads allowing multiple tasks to operate in parallel. Starting with HONEYCOMB, tasks are executed on a single thread to avoid common application errors caused by parallel execution.

If you truly want parallel execution, you can invoke executeOnExecutor(java.util.concurrent.Executor, Object[]) with THREAD_POOL_EXECUTOR

You can use code like this on most devices

if (Build.VERSION.SDK_INT >= 11) {
    asyncTask.executeOnExecutor(AsyncTask.THREAD_POOL_EXECUTOR);
} else {
    asyncTask.execute();
}

or even create a custom ThreadPoolExecutor.