×

Fast Fourier analysis for \(SL_ 2\) over a finite field and related numerical experiments. (English) Zbl 0773.65091

Let \(G:=SL_ 2(F_ q)\). The authors prove that the minimal number of arithmetic operations to compute a Fourier transform of \(f\in L^ 2(G)\) and to recover \(f\) via Fourier inversion is \(O(q^ 2\log q)\), respectively. The result is based on the fact that \(G\) contains the metabelian subgroup of upper triangular matrices and on symmetry adapted fast Fourier transforms.
The paper builds up on M. Clausen [SIAM J. Comput. 18, No. 3, 584- 593 (1989; Zbl 0677.68028)] and previous results of the second author [Adv. Appl. Math. 11, No. 2, 164-204 (1990; Zbl 0709.65126)]. The computation of the relevant Fourier transform permits extensive numerical investigations of the spectra of families of Cayley graphs on \(G\).
Reviewer: G.Steidl (Rostock)

MSC:

65T40 Numerical methods for trigonometric approximation and interpolation
65Y20 Complexity and performance of numerical algorithms
65J10 Numerical solutions to equations with linear operators
43A25 Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20C15 Ordinary representations and characters
PDFBibTeX XMLCite
Full Text: DOI EuDML EMIS

References:

[1] Alon N., Combinatorica 6 pp 83– (1983) · Zbl 0661.05053
[2] Alon N., J. Combin. Theory 38 pp 73– (1985) · Zbl 0549.05051
[3] Baum U., Doctoral dissertation, in: ”Existence and efficient construction of fast Fourier transforms on supersolvable groups” (1991)
[4] Baum U., SIAM J. Comput. 20 pp 451– (1991) · Zbl 0729.65115
[5] Baum U., Applicable Algebra in Engineering, Communication and Computing 2 pp 35– (1991) · Zbl 0734.65103
[6] Bien F., Notices of the AMS 36 (1) pp 5– (1989)
[7] Biggs N., Algebraic Graph Theory (1974) · Zbl 0797.05032
[8] Brooks R., ”Some relations between spectral geometry and number theory” (1991)
[9] Bshouty N., J. of Algorithms 9 pp 354– (1988) · Zbl 0653.65032
[10] Buck M. W., SIAM J. Algebraic and Discrete Methods 7 pp 282– (1986) · Zbl 0612.68061
[11] Chung F., J. Amer. Math. Soc. 2 pp 187– (1989)
[12] Clausen M., J. Theor. Comp. Sci. 67 pp 55– (1989) · Zbl 0677.65143
[13] Clausen M., SIAM J. Comput. 18 pp 584– (1989) · Zbl 0677.68028
[14] Diaconis P., Group Representations in Probability and Statistics (1988) · Zbl 0695.60012
[15] Diaconis P., J. Amer. Math. Soc. 3 pp 297– (1990)
[16] Dickson L., Linear Groups with an Exposition of the Galois Field Theory (1958) · Zbl 0082.24901
[17] Jordan H., Amer. J. Math. 29 pp 387– (1907) · JFM 38.0175.01
[18] Kesten H., Trans. Amer. Math. Soc. 92 pp 336– (1959)
[19] Kantor W., Georn. Ded. 36 pp 67– (1990)
[20] Kloosterman H. D., Ann. of Math. 47 pp 317– (1946) · Zbl 0063.03262
[21] Lenstra A. K., Handbook of Theoretical Computer ScienceA: Algorithms and Complexity pp 673– (1990)
[22] Lubotzky A., ”Discrete groups, expanding graphs, and invariant measures” · Zbl 1183.22001
[23] Naimark M. A., Theory of Group Representations (1980)
[24] Piatetski-Shapiro I., Complex Representations of GL[2, K] for Finite Fields K (1983) · Zbl 0513.20026
[25] Rockmore D., Adv. in Appl. Math. 11 pp 164– (1990) · Zbl 0709.65126
[26] Rockmore D., ”Efficient computation of Fourier inversion for finite groups” (1990) · Zbl 0709.65125
[27] Sarnak P., Some Applications of Modular Forms (1990) · Zbl 0721.11015
[28] Schur I., J. Reine Angew. Math. 132 pp 85– (1907)
[29] Serre J. P., Linear Representations of Finite Groups (1977) · Zbl 0355.20006
[30] Silberger A., Osaka J. Math. 6 pp 329– (1969)
[31] Suzuki M., Group Theory, volume I (1982)
[32] Tanaka S., Osaka J. Math. 4 pp 65– (1967)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.