Firstly current tech and widely accepted theories:
Unfortunately the key point in this question is:
Is the only way to make this jump, to reduce the relative speed
The answer is yes. It really comes down to conservation of momentum, or more specifically conservation of angular momentum.
Your spacecraft at Earth has a fixed angular momentum around the sun. A few points people often think can get around this:
1) It doesn't matter how you change the attitude of your spacecraft the angular moment stays the same.
2) If you give the spacecraft angular momentum along a different axis so that it goes around the sun in a polar orbit it still won't have the right angular momentum when it gets to 180deg from it's starting position because it still has its original angular momentum.
In essence if you wish to match velocity with retrograde Mars then you will need to reverse your angular momentum vector (and increase the magnitude).
Now the more interesting concepts that may be able to short circuit the problem:
The first unusual method that springs to mind is an Alcubierre drive, mainly due to that question being asked recently. It seems to me that you would be able to shift your spacecraft to the opposite side of the sun using such a drive. At which point the spacecraft would be moving in the same direction as retrograde Mars IF the Alcubierre drive can transport an object in one dimension (eg X direction) whilst the object has a velocity perpendicular. I don't seem any immediate reason why this type of drive wouldn't work here (or at least no more reason than it working anywhere else) so this is a possibility.
The second unusual method that springs to mind is the very sci-fi idea of wormholes. In theory a wormhole could be exist connecting opposite sides of the sub where the relative velocity of the two objects would be much closer. Similar to the Alcubierre drive in a way. A problem here is that some current thinking on wormholes is that they are very small. We're talking the same scale as the Planck length for the neck of the wormhole. Also good luck trying to create one; this patent should get you started!