Algorithms for Unitary Representations of Finite Groups Given a $d$-dimensional $\mathbb C$-linear representation of a finite group $G$, i.e. $\pi \!: G \to \mathrm {GL}_d(\mathbb C)$, one can use Weyl's unitary trick to construct an inner product $\langle v, w\rangle_\mathrm U$ for $v, w \in \mathbb C^d$ under which that representation is unitary.  To do so, one begins an arbitrary inner product $\langle v, w\rangle_a$, such as the trivial $\langle v, w\rangle_1 = v^\dagger w$, and calculates
$$ \langle v, w\rangle_\mathrm U = \frac 1 {|G|} \sum_{g \in G} \left \langle \pi (g) v, \pi(g) w \right \rangle_a. $$
Now, $\forall g,\,v \! : \, \langle \pi(g) v, \pi(g) v\rangle_\mathrm U = \langle v, v\rangle_\mathrm U$.
Naïvely, evaluating such an inner product requires $O(d^3|G|)$ multiplications, which quickly becomes infeasible for non-trivial representations of interesting groups.  Can anyone suggest a way to use the group structure to reduce the $|G|$ factor in the complexity of this algorithm?  Alternatively, any efficient way to calculate an equivalent representation which is unitary under the trivial inner product $\langle v, w\rangle_1$, so $\forall g \! : \, \pi(g) \in \mathrm U(d)$, would suit my needs as well.
 A: I hate to answer my own question less than twenty-four hours after posting it, but I've found a solution.  Using a small number of group elements $g_1, \ldots g_n \in G$ and the standard orthornormal basis $\mathbf B = \left [ \mathbf e_j \in \mathbb C^d \! : \, j \in 1, \ldots, d \, \right ]$, one can construct constraints on a satisfactory inner product $ \left \langle \pi \! \left ( g_i \right ) \mathbf e_j, \pi \! \left ( g_i \right ) \mathbf e_k \right \rangle_\mathbf U = \left \langle \mathbf e_j, \mathbf e_k \right \rangle_\mathbf U$.
In my test case, the two non-orthogonal generators $g_1$ and $g_2$ of a 20-dimensional $\mathbb R$-linear representation of the $\mathrm M_{11}$ sporadic group (of orders two and four, respectively) were sufficient to solve for the real symmetric matrix elements of a satisfactory inner product, up to normalization.
From there, one can perform a change of basis on $\pi$ from an orthonormal basis (e.g. constructed using the Gram–Schmidt process) with respect to $\langle v, w \rangle_\mathbf U$ to the standard basis $\mathbf B$, which is orthonormal with respect to the trivial inner product $\langle v, w \rangle_1 $, to get a representation which is in $\mathbf U(d)$.
Update:$\:$ The rank of the constraints from $g_1$ alone is 96, while that of $g_2$ is 154.  Together, they get 209 of the $210 = d(d + 1)/2$ independent matrix elements of the unitary inner product, leaving only the normalization unfixed.
Update 2:$\:$  From my "simple" $\mathrm M_{11} \! \to \mathrm{SL}_{20}(\mathbb R)$ test case, it seems like the constraint ranks are a function of the element's conjugacy class.  I calculated:

*

*$\hphantom{1} 1A \hphantom{/B} : \: \: \hphantom{00} 0$

*$\hphantom{1} 2A \hphantom{/B} : \: \: \hphantom{0} 96$

*$\hphantom{1} 3A \hphantom{/B} : \: \: 138$

*$\hphantom{1} 4A \hphantom{/B} : \: \: 154$

*$\hphantom{1} 5A \hphantom{/B} : \: \: 168$

*$\hphantom{1} 6A \hphantom{/B} : \: \: 170$

*$\hphantom{1} 8A/B : \: \: 182$

*$11A/B : \: \: 190$
I was, unfortunately, unable to relate to relate these values to the character table in any meaningful way, although they seem like a somewhat interesting, albeit representation-dependent, "class function", in the group-theoretic sense.
Update 3:$\:$  My method takes about a minute for representations to $\mathrm {GL}_{77} (\mathbb Z)$.  Meanwhile, for a 77-dimensional, absolutely irreducible, $\mathbb Z$-linear representation of the sporadic, pariah, finite simple group $\mathrm J_1$, Magma's InvariantForms finds an valid inner product in $80\,\mathrm {ms}$.  As their software is closed source, I don't know what algorithm they're using.  I'll have to do more research regarding invariant forms.  I've also contacted Magma's developers for a mostly unrelated reason, but included a side-question asking how the InvariantForms function works.
Any further insight would be appreciated.
