  The relativistic magnetohydrodynamics (RMHD) set of equations has recently
seen increased use in astrophysical computations. Even so, RMHD codes remain
fragile. The reconstruction can sometimes yield superluminal velocities in
certain parts of the mesh. In this paper we present a reconstruction strategy
that overcomes this problem by making a single conservative to primitive
transformation per cell followed by higher order WENO reconstruction on a
carefully chosen set of primitives that guarantee subluminal reconstruction of
the flow variables. For temporal evolution via a predictor step we also present
second, third and fourth order accurate ADER methods that keep the velocity
subluminal during the predictor step. The RMHD system also requires the
magnetic field to be evolved in a divergence-free fashion. In the treatment of
classical numerical MHD the analogous issue has seen much recent progress with
the advent of multidimensional Riemann solvers. By developing multidimensional
Riemann solvers for RMHD, we show that similar advances extend to RMHD. As a
result, the face-centered magnetic fields can be evolved much more accurately
using the edge-centered electric fields in the corrector step. Those
edge-centered electric fields come from a multidimensional Riemann solver for
RMHD which we present in this paper. In this paper we also develop several new
test problems for RMHD. We show that RMHD vortices can be designed that
propagate on the computational mesh as self-preserving structures. These RMHD
vortex test problems provide a means to do truly multidimensional accuracy
testing for RMHD codes. Several other stringent test problems are presented. We
show the importance of resolution in certain test problems. Our tests include a
demonstration that RMHD vortices are stable when they interact with shocks.
