We investigate the optimal power allocation in an OFDM-SDMA system when some users have minimum requirements for their downlink transmission rate. We first solve the unconstrained problem for which we propose a fast zero-finding technique that is guaranteed to find an optimal solution, and an approximate algorithm that has lower complexity but is not guaranteed to converge. For the more complex rate-constrained problem, we propose two approximate algorithms. One is an iterative technique that finds an optimal solution on the rate boundaries so that the solution is feasible, but not necessarily optimal. The other is not iterative but cannot guarantee a feasible solution. We present numerical results showing that the computation time for the iterative heuristic is about one order of magnitude faster than finding the exact solution with a numerical solver, and the non-iterative technique is an additional order of magnitude faster than the iterative heuristic. We also show that in most cases, the amount of infeasibility with the non-iterative technique is small enough that it could probably be used in practice.