I have found a GPL library (no dual license), which does exactly what I need. Unfortunately, the GPL license on the library is incompatible with the license of a different library I use. I have therefore decided to rewrite the GPL library, so the license can be changed.
My question is: How extensive do the changes need to be to the library in order to be able to change the license? In other words, what is the cheapest way to do this?
I'm not a lawyer, but AFAIK if you have seen the GPLed library code any emulation library you write would be tainted and may be declared a derived work by a judge if it is too similar in his appreciation.
So the process would be to write a functional spec and have someone which hasn't seen the GPLed code write the library.
Edit: Note that with the way you formulate your question "How extensive do the changes need to be to the library in order to be able to change the license?" the answer is AFAIK clear: whatever you do, if you just modify the library you must respects the term of the license which makes you able to modify it in the first place.
The usual way round this problem is to first contact the library's owner and ask if they will release it to you under a different licence.
If you're working on an open source project where the GPL is not compatible, then there's a good chance they'll do this, some projects end up with a GPL licence just because it seemed like the best choice.
Of course, this applies to both libraries. Getting the permissive licence dual-licences under a less permissive one shouldn't be a problem.
If you're working with a commercial product, then many library authors will give you a release under a different licence, if you compensate them appropriately.
My understanding is that if you start with a work and modify it, no matter how extensive the modifications, the final result is a derived work of the original. You will need to write the library from scratch. If you write the library from scratch, but have seen the code, then if it is too similar you can again be sued for copyright infringement.
These rules are not specific to software, they apply to copyrightable things of all kinds.
I am not a lawyer, and this is not legal advice. I am also quite possibly not in your jurisdiction, and you should always be dubious of legal advice offered on the Internet. If you wish to have reliable legal advice, you'll need to pay a lawyer.
IANAL, but I do know that in the USA, no degree of modification will create a non-derivative work. If it has any code copied from the old library or it has enough internal similarity that it would get you in trouble for plagiarisim in a University class, then you are no-where near a new work. Changing some names of functions or variables won't do anything, neither will moving chunks of code around in the source. You would have to independently re-create it to even stand a chance. IOWs, you'd need to look only at the interfaces that it provides, and decide how to provide that functionality and re-create it that way to stand a chance. Even then you still might not be out of the woods if someone really cares and gets mad.
In the end, your best bet is to contact the author of the library and hope that you can find an arrangement for more permissive licensing of he library.
If everything else suggested here (asking for double license, rewriting) is not acceptable, please remember that it is still not a clear case whether or not dynamic linking with proprietary program/library is considered derivative work. FSF says it is, but many lawyers (Lawrence Rosen included) have questioned this.
So you can link your software with GPLed library, then make sure source code for it is distributed with every copy of your software. If anybody sues you, they have to prove, that their understanding of this tricky and murky GPL aspect is correct. As it appears (eg. Galoob vs Nintendo) you can't be absolutelly sure what makes derivative work and what doesn't.
The only way it would not be derived work, would be if you'd rewrite whole code yourself without using any of the original code. Which is probably infeasible.
There are much easier ways around GPL:
Also note, that GPL is distribution license, so you only need to license your work if you distribute binaries to third party. And you're only obliged to release source to them, no obligation to release it to general public, unless you release binaries to general public. If you're using your code for example only on your servers, you have no obligation to release any code. This is how for example Google does it with their tweaked Linux kernels.
IANAL and, in any case, this may mean nothing legally, but, I believe that in Steven Levy's book "Hackers", he describe how, at one point, RMS wrote *nix code for money during the day and at night wrote the same stuff at home so that it could be part of... GNU?... this was before Linux... some free Unix type system. I believe that he had to make the home-code different than the day-code, but he was basically doing exactly what you are suggesting.
This probably doesn't matter legally, either but... I am not sure whether Apple and/or Microsoft got permission/license or something, but didn't bell labs invent the desktop/icon/mouse interface, which was used for Macs (or Lisa?) which was then used by Microsoft.
There is no answer to this except for a trial before a judge in your particular jurisdiction. But do you want to risk it? Or go to the effort of re-writing the GPL library, the tests etc. etc. Are you sure the other library is incompatible with the GPL? This is actually quite unusual, unless you want to distribute both libraries under the non-GPL libraries terms.
How extensive do the changes need to be to the library in order to be able to change the license?
In most parts of the world you need to start from scratch and not cut and past anything. You need new names for functions/classes/variables etc etc, and the structure should be different. Then you are safe.
On the other hand, if a diff-tool can't find any similarities then...
