The efficient computation of Fourier transforms on semisimple algebras. (English) Zbl 1530.65189
In this article, the problem of the efficient computation of a Fourier transform on a finite-dimensional complex semisimple algebra is discussed. The authors present a general approach to the construction of efficient algorithms for computing a Fourier transform on a semisimple algebra and give a general result (Theorem 4.5) to find efficient Fourier transforms on a finite dimensional semisimple algebra with special subalgebra structure. Particular results include highly efficient algorithms for the Brauer, Temperley-Lieb and Birman-Murakami-Wenzl algebras. To obtain these results the authors use a connection between Bratteli diagrams, the derived path algebra and the construction of Gelfand-Tsetlin bases.
Reviewer: S. F. Lukomskii (Saratov)
MSC:
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
| 20C15 | Ordinary representations and characters |
| 43A30 | Fourier and Fourier-Stieltjes transforms on nonabelian groups and on semigroups, etc. |
References:
| [1] | Baum, U., Existence and efficient construction of fast Fourier transforms for supersolvable groups, Comput. Complex., 1, 235-256, (1991) · Zbl 0778.65092 · doi:10.1007/BF01200062 |
| [2] | Baum, U.; Clausen, M.; Tietz, B., Improved upper complexity bounds for the discrete Fourier transform, Appl. Algebra Eng. Commun. Comput., 2, 35-43, (1991) · Zbl 0734.65103 · doi:10.1007/BF01810853 |
| [3] | Benkart, G.; Ram, A.; Shader, C., Tensor product representations for orthosymplectic Lie superalgebras, J. Pure Appl. Algebra, 130, 1-48, (1998) · Zbl 0932.17008 · doi:10.1016/S0022-4049(97)00084-4 |
| [4] | Beth, T., On the computational complexity of the general discrete Fourier transform, Theor. Comput. Sci., 51, 331-339, (1987) · Zbl 0629.68041 · doi:10.1016/0304-3975(87)90041-7 |
| [5] | Birman, J.; Wenzl, H., Braids, link polynomials and a new algebra, Trans. Am. Math. Soc., 313, 249-273, (1989) · Zbl 0684.57004 · doi:10.1090/S0002-9947-1989-0992598-X |
| [6] | Bracewell, R.N.: The Fourier Transformation and Its Applications, 2nd edn. McGraw-Hill, New York (1978) · Zbl 0502.42001 |
| [7] | Bürgisser, P., Clausen, M., Shokrollahi, M.: Algebraic Complexity Theory. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315. Springer, Berlin (1997). With the collaboration of Thomas Lickteig · Zbl 1087.68568 · doi:10.1007/978-3-662-03338-8 |
| [8] | Clausen, M., Fast generalized Fourier transforms, Theor. Comput. Sci., 67, 55-63, (1989) · Zbl 0677.65143 · doi:10.1016/0304-3975(89)90021-2 |
| [9] | Cooley, JW, The re-discovery of the fast Fourier transform algorithm, Mikrochim. Acta, III, 33-45, (1987) · doi:10.1007/BF01201681 |
| [10] | Cooley, J.; Tukey, J., An algorithm for the machine calculation of complex Fourier series, Math. Comput., 19, 297-301, (1965) · Zbl 0127.09002 · doi:10.1090/S0025-5718-1965-0178586-1 |
| [11] | Diaconis, P., Average running time of the fast Fourier transform, J. Algorithms, 1, 187-208, (1980) · Zbl 0445.68029 · doi:10.1016/0196-6774(80)90022-X |
| [12] | Diaconis, P., A generalization of spectral analysis with application to ranked data, Ann. Stat., 17, 949-979, (1989) · Zbl 0688.62005 · doi:10.1214/aos/1176347251 |
| [13] | Diaconis, P.; Rockmore, D., Efficient computation of the Fourier transform on finite groups, J. Am. Math. Soc., 3, 297-332, (1990) · Zbl 0709.65125 · doi:10.1090/S0894-0347-1990-1030655-4 |
| [14] | Diaconis, P.; Ram, A., Analysis of systematic scan metropolis algorithms using Iwahori-Hecke algebra techniques, Mich. Math. J., 48, 157-190, (2000) · Zbl 0998.60069 · doi:10.1307/mmj/1030132713 |
| [15] | Elliott, D., Rao, K.: Fast Transforms: Algorithms, Analyses, Applications. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York (1982) · Zbl 0562.65097 |
| [16] | Flath, D.; Halverson, T.; Herbig, K., The planar rook algebra and pascal’s triangle, Enseign. Math. (2), 55, 77-92, (2009) · Zbl 1209.20004 · doi:10.4171/LEM/55-1-3 |
| [17] | Goodman, FM; Wenzl, H., The Temperley-Lieb algebra at roots of unity, Pac. J. Math., 161, 307-334, (1993) · Zbl 0823.16004 · doi:10.2140/pjm.1993.161.307 |
| [18] | Goodman, F.; Hauschild, H., Affine Birman-wenzl-murakami algebras and tangles in the solid torus, Fund. Math., 190, 77-137, (2006) · Zbl 1100.57008 · doi:10.4064/fm190-0-4 |
| [19] | Goodman, F., de la Harpe, P., Jones, V.: Coxeter Graphs and Towers of Algebras. Mathematical Sciences Research Institute Publications, vol. 14. Springer, New York (1989) · Zbl 0698.46050 · doi:10.1007/978-1-4613-9641-3 |
| [20] | Grood, C., The rook partition algebra, J. Comb. Theory A, 113, 325-351, (2006) · Zbl 1082.05095 · doi:10.1016/j.jcta.2005.03.006 |
| [21] | Halverson, T.; Ram, A., Characters of algebras containing a Jones basic construction: the Temperley-Lieb, okada, Brauer, and Birman-wenzl algebras, Adv. Math., 116, 263-321, (1995) · Zbl 0856.16038 · doi:10.1006/aima.1995.1068 |
| [22] | Halverson, T.; del Mas, E., Representations of the rook-Brauer algebra, Commun. Algebra, 42, 423-443, (2014) · Zbl 1291.05215 · doi:10.1080/00927872.2012.716120 |
| [23] | Kassel, C., Turaev, V.: Braid Groups. Graduate Texts in Mathematics, vol. 247. Springer, New York (2008). With the graphical assistance of Olivier Dodane · Zbl 1208.20041 · doi:10.1007/978-0-387-68548-9 |
| [24] | Kondor, R.; Barber, D. (ed.); Taylan Cemgil, A. (ed.); Silvia, C. (ed.), Non-commutative harmonic analysis in multi-object tracking, 277-284, (2011), Cambridge · doi:10.1017/CBO9780511984679.014 |
| [25] | Lafferty, JD; Rockmore, D., Fast Fourier analysis for \({{\rm SL}}_2\) over a finite field and related numerical experiments, Exp. Math., 1, 115-139, (1992) · Zbl 0773.65091 · doi:10.1080/10586458.1992.10504252 |
| [26] | Leduc, R.; Ram, A., A ribbon Hopf algebra approach to the irreducible representations of centralizer algebras: the Brauer, Birman-wenzl, and type A Iwahori-Hecke algebras, Adv. Math., 125, 1-94, (1997) · Zbl 0936.17016 · doi:10.1006/aima.1997.1602 |
| [27] | Malandro, ME, Fast Fourier transforms for finite inverse semigroups, J. Algebra, 324, 282-312, (2010) · Zbl 1197.65235 · doi:10.1016/j.jalgebra.2009.11.031 |
| [28] | Malandro, ME, Inverse semigroup spectral analysis for partially ranked data, Appl. Comput. Harmon. Anal., 35, 16-38, (2013) · Zbl 1297.62197 · doi:10.1016/j.acha.2012.07.009 |
| [29] | Malandro, ME; Fast, RDN, Fourier transforms for the rook monoid, Trans. Am. Math. Soc., 362, 1009-1045, (2010) · Zbl 1264.65220 · doi:10.1090/S0002-9947-09-04838-7 |
| [30] | Maslen, D., The efficient computation of Fourier transforms on the symmetric group, Math. Comput., 67, 1121-1147, (1998) · Zbl 0902.20005 · doi:10.1090/S0025-5718-98-00964-8 |
| [31] | Maslen , D., Rockmore, D.: Generalized FFTs—a survey of some recent results. In: Groups and Computation, II (New Brunswick, NJ, 1995). DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, vol. 28, pp. 183-237. American Mathematical Society, Providence (1997) · Zbl 0892.20008 |
| [32] | Maslen, D.; Rockmore, D., Separation of variables and the computation of Fourier transforms on finite groups. I, J. Am. Math. Soc., 10, 169-214, (1997) · Zbl 0860.20016 · doi:10.1090/S0894-0347-97-00219-1 |
| [33] | Maslen, D.; Rockmore, D., Double coset decompositions and computational harmonic analysis on groups, J. Fourier Anal. Appl., 6, 349-388, (2000) · Zbl 0960.43006 · doi:10.1007/BF02510144 |
| [34] | Maslen, D.; Rockmore, D., The cooley-tukey FFT and group theory, Not. Am. Math. Soc., 48, 1151-1160, (2001) · Zbl 1128.20300 |
| [35] | Maslen, David; Rockmore, Daniel N.; Wolff, Sarah, Separation of variables and the computation of Fourier transforms on finite groups, II, Journal of Fourier Analysis and Applications, 24, 226-284, (2016) · Zbl 1384.43001 · doi:10.1007/s00041-016-9516-4 |
| [36] | Morton, H., Wasserman, A.: A Basis for the Birman-Wenzl Algebra, p. 29, revised 2000, unpublished manuscript. arXiv:1012.3116 (1989) |
| [37] | Munthe-Kaas, HZ, On group Fourier analysis and symmetry preserving discretizations of pdes, J. Phys. A, 39, 5563-5584, (2006) · Zbl 1090.65121 · doi:10.1088/0305-4470/39/19/S14 |
| [38] | Murakami, J., The kauffman polynomial of links and representation theory, Osaka J. Math., 24, 745-758, (1987) · Zbl 0666.57006 |
| [39] | Ram, A.: Representation Theory and Character Theory of Centralizer Algebras. ProQuest LLC, Ann Arbor (1991). PhD thesis, University of California, San Diego |
| [40] | Ram, A., Seminormal representations of Weyl groups and Iwahori-Hecke algebras, Proc. Lond. Math. Soc. (3), 75, 99-133, (1997) · Zbl 0876.20010 · doi:10.1112/S0024611597000282 |
| [41] | Ridout, D.; Saint-Aubin, Y., Standard modules, induction and the structure of the Temperley-Lieb algebra, Adv. Theor. Math. Phys., 18, 957-1041, (2014) · Zbl 1308.82015 · doi:10.4310/ATMP.2014.v18.n5.a1 |
| [42] | Rockmore, D., Fast Fourier analysis for abelian group extensions, Adv. Appl. Math., 11, 164-204, (1990) · Zbl 0709.65126 · doi:10.1016/0196-8858(90)90008-M |
| [43] | Rockmore, D.: Some applications of generalized FFTs. In: Groups and Computation, II (New Brunswick, NJ, 1995). DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 28, pp. 329-369. American Mathematical Society, Providence (1997) · Zbl 0892.20009 |
| [44] | Rockmore, D., The FFT: an algorithm the whole family can use, Comput. Sci. Eng., 2, 60-64, (2000) · doi:10.1109/5992.814659 |
| [45] | Rotman, J.J.: Advanced Modern Algebra. Prentice Hall Inc., Upper Saddle River (2002) · Zbl 0997.00001 |
| [46] | Rui, H., A criterion on the semisimple Brauer algebras, J. Comb. Theory A, 111, 78-88, (2005) · Zbl 1095.16006 · doi:10.1016/j.jcta.2004.11.009 |
| [47] | Wenzl, H., On the structure of brauer’s centralizer algebras, Ann. Math. (2), 128, 173-193, (1988) · Zbl 0656.20040 · doi:10.2307/1971466 |
| [48] | Wolff, S.: Random walks on the BMW monoid: an algebraic approach (in preparation) · Zbl 1427.60015 |
| [49] | Wood, J.: Some applications of the Fourier transform in algebraic coding theory. In: Algebra for Secure and Reliable Communication Modeling. Contemporary Mathematics, vol. 642, pp. 1-40. American Mathematical Society, Providence (2015) · Zbl 1360.94388 |
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.
