In the days before [W, TW, BCDT], how did people show that specific elliptic curves over $\mathbb{Q}$ were modular? For instance, I was reading through a paper of Buhler, Gross and Zagier from 1985 on the curve 5077a, and they say that modularity can be checked by a finite computation in the 422dimensional space of cuspforms of weight 2 and level 5077 (and remark at the end that Serre and Mestre have checked it). A google search brought up the name "FaltingsSerre method": was this the technique of choice? Also, are there any good references for it?

1$\begingroup$ Could you please explain who do you mean by W, TW and BCDT? I just recoqnize Brian Conrad and Wiles ... $\endgroup$ – Martin Brandenburg Feb 13 '11 at 12:33

3$\begingroup$ I'm referring to the papers by Wiles, TaylorWiles, and BreuilConradDiamondTaylor. $\endgroup$ – Abhinav Kumar Feb 13 '11 at 14:05
They explicitly computed quotients of $X_0(N)$ and identified them with elliptic curves. Suppose you can compute the space $S_2(\Gamma_0(N),\mathbf{C})$ of modular forms. An (isogeny class of) elliptic curves of conductor $N$ corresponds (by modularity) to a normalized new Hecke eigenform with coefficients in $\mathbf{Z}$. Given such an $f$, one can compute the periods of $f$, which allows one to write down a Weierstrass equation for $f$. If one can do this in such a way to guarantee that the coefficients of the Weierstrass equation are integers, this allows one to computationally determine exactly the modular elliptic curves of conductor $N$. All this is very well explained in Cremona's book, which is available free online:
http://www.warwick.ac.uk/~masgaj/book/amec.html
The particular method referred to in the paper of [BGZ] was presumably the "method of graphs", see for example here:
http://modular.math.washington.edu/msri06/refs/mestremethodofgraphs/mestreen.pdf
The FaltingsSerre method is slightly different; it allows you to determine, given two Galois representations $\rho_1$ and $\rho_2$ from $G_{K}$ to (say) $\mathrm{GL}_n(\mathbf{Z}_p)$ such that:
$\overline{\rho}_1 \simeq \overline{\rho}_2$,
$\rho_1$ and $\rho_2$ are both unramified outside some finite (given) set of places $S$ of $K$.
whether $\rho_1 \simeq \rho_2$. You could use it to prove that an elliptic curve $E/\mathbf{Q}$ is modular by comparing the Galois representation attached to the $p$adic Tate module of $E$ and the Galois representation attached to the conjecturally corresponding eigenform of level $N$ (EDIT: this works because the Galois representation determines the isogeny class of $E$ by Faltings' proof of the Tate conjecture for abelian varieties). However, this wouldn't be so efficient. However, there are other situations (for example, elliptic curves over other number fields) where the corresponding automophic form is not enough to compute the periods. In this case, the FaltingsSerre method can be used to prove modularity. Taylor uses this to prove that a certain elliptic curve over $\mathbf{Q}(\sqrt{3})$ is modular.

1$\begingroup$ For those who prefer to read Mestre in French, William Stein's site has the original too: $$ $$ boxen.math.washington.edu/msri06/refs/mestremethodofgraphs/… $$ $$ $\endgroup$ – Chandan Singh Dalawat Feb 15 '11 at 13:58

$\begingroup$ There is also a paper of Dieulefait, Guerberoff and Pacetti (see arxiv.org/abs/0804.2302) where they use the FaltingsSerre method to prove modularity of some elliptic curves over imaginary quadratic fields. $\endgroup$ – Nicolas B. Nov 23 '11 at 8:50
The general "standard approach" was to use the suite of algorithms described in Cremona's book (which is now freely available). The basic idea is to use modular symbols to write down a basis for the homology of the modular curve $X_0(N)$, then use the action of Hecke operators to compute all of the rational cuspidal newforms of level $N$. To each newform there is a corresponding optimal elliptic curve quotient of $X_0(N)$, whose equation can be analytically computed exactly (this uses Edixhoven's remark that the Manin constant is an integer); once that optimal curve has been computed there are standard formulas to list all curves isogenous to it. Thus to prove that a given elliptic curve $E$ is modular, first compute its conductor $N$ (using Tate's algorithm), then enumerate all the modular elliptic curves of conductor $N$ (via Cremona's algorithm), and finally note that $E$ is in this list.
If you're interested in efficiency there are shortcuts, e.g., instead of finding all rational newforms, just find the one that looks like it comes from your curve $E$.

$\begingroup$ Thanks for your answers, William and Wanax! William: it seems I can only accept one answer, so accepting Wanax's because of its multiple references. Hope you don't mind! $\endgroup$ – Abhinav Kumar Feb 13 '11 at 6:32

1$\begingroup$ Regarding complexity, I just mentioned this post to Cremona and he remarks: "...and doing level 5077 takes under 1 second now" $\endgroup$ – William Stein Feb 13 '11 at 6:52

2$\begingroup$ @Abhinav: Amusingly, Wanax's one extra reference is to a paper hosted on my website that I got a student to translate into English. :) (I don't care about the points stuff.) $\endgroup$ – William Stein Feb 13 '11 at 22:48
The answer is outlined in Don Zagier's 1985 paper Modular points, modular curves, modular surfaces and modular forms.