Posts tagged ‘algebra’

Why can we have a Fast Fourier Transform ?

The Fourier transform was introduced by Fourier as a tool to solve heat equations, but is now used in its discrete version throughout the computing world more than trillions of times each second. It is probably more, I was assuming an average computer does billions of Discrete Cosine Transforms per day for Web browsing (JPEG images and Youtube) and music listening, but how huge is the contribution of millions of people watching MPEG-2 compressed television programs on satellite or terrestrial digital broadcasting?

It is thus important to know that the Fourier transform (which is always the Fast Fourier Transform) is really fast (especially when it is dozens, hundreds of times faster than the natural algorithm). I am not yet sure about the fast versions of variants of the discrete transform (cosine transforms and its friends), but I guess they can be derived from the classical case.

What is it ?

The classical Fourier transform takes a T-periodic function f and computes for each integer n the integral

f_n = \frac 1 {\sqrt T} \int_0^T f(t) \exp(-ni\omega t) dt

where \omega = 2\pi/T. It separates f into components having period T/n, and has the property that the energy E(f) = \frac 1 T \int |f(t)|^2 dt is the sum \sum |f_k|^2.

The discrete Fourier transform takes a discrete function given by x = (x_0, x_1, \dots, x_{n-1}) and computes the discrete analogue

y_p = \sum_{q = 0}^{n-1} x_q \exp(-2i\pi \frac{pq}{n})


12 March 2009 at 3:23 pm 3 comments

Monads in mathematics 4 : the bar and cobar constructions

The use of monads and comonads in homological algebra is as old as the theory: Godement’s standard construction refers to the use of monads in cohomology theory, and is said to be the first study of a general method for constructing acyclic resolutions. Later the theory was explored in greater depth by Eilenberg, Moore, Barr, Beck. The term bar resolution is now most commonly used to describe the process. Monads derived from operads were also studied by Lawvere, Mitchell, Bénabou, under the name of algebraic theories, with aim towards topoi and logic.

Bar resolutions (see J. Baez website and the LNM Seminar on Triples and Categorical Homology Theory) are a way to canonically (i.e. functorially) describe an arbitrary algebra over a monad using only free algebras. It is a particular case of definition with generators and relations which is often the only way to describe infinite mathematical objects with finite expressions (computer algebra systems usually deal with finitely generated objects, and use generators and relations to describe their elements), but bar resolutions somehow are the universal way of doing this.

Most cohomology theories fit in the framework of bar constructions, though in various apparently unrelated ways. However, a visible common denominator of most constructions is the use of simplicial methods. This makes them of some use in homotopical algebra: bar resolutions are used to define canonical cofibrant resolutions of objects, which explains their uses in definition of derived functors.

4 March 2009 at 10:39 pm Leave a comment

Rational approximations of √2

Introducing undergraduates to rational approximations of √2 can be an opportunity to insidiously tell them about many parts of mathematics they certainly don’t want to hear about. In a less pessimistic way, I would say this is a nice way to illustrate the use of several theories in abstract mathematics.

First, you may want to tell them it is not a rational number, which could be easy, unless they never heard about factoring integers.

Then, you could use classical sequences from high school classes: it is easy to check that iterating u_{n+1} = \frac{u_n+2}{u_n+1} converges to ±√2, and setting U_n = \frac{u_n-\sqrt 2}{u_n+\sqrt 2} they will even be able to give an explicit formula with a geometric sequence. There is of course a well-known algorithm which speeds up considerably the computation : Newton’s method. This can be illustrated geometrically by drawing the graph of a function having √2 as a root (for example x \mapsto x^2-2):

  1. take a rough approximation, such as x=1
  2. imagine the function is affine (replacing the graph by its tangent)
  3. use the approximation of the function to calculate an approximation of the solution
  4. use this newly found rough solution to iterate from step 1

This method requires iterating v_{n+1} = \frac 1 2 (v_n + 2/v_n), and converges considerably faster. Both methods yield sequences of rational numbers converging to √2, so should be considered as methods to obtain fractional numbers giving good approximations of √2. (more…)

23 February 2009 at 5:23 pm Leave a comment

Réprésentations de l’algèbre de Lie sl(2)

Alors que la géométrie mettait autrefois en avant l’importance des groupes et des transformations d’un objet (une philosophie défendue notamment par Klein), l’influence croissante de la mécanique, l’algèbre et l’analyse tend à remplacer la théorie des groupes par celle des algèbres de Lie. La théorie de Lie, développée par Borel et Chevalley permet d’étudier les représentations de certains groupes à travers leurs algèbres de Lie, et la géométrie différentielle en est également friande.

Whereas geometry in its old times would highlight the importance of groups of transformations (as in the Erlangen program introduced by Klein), modern developments in mechanics, algebra and calculus would rather use the language of Lie algebra. Lie theory was actively developed by Borel and Chevalley, allowing to understand groups through their Lie algebras, and differential geometry is closely related to this subject as well.

Le groupe SL2

Le groupe SL2 est le groupe constitué des matrices \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} telles que ad-bc = 1. L’inverse d’une telle matrice est donné par \begin{pmatrix} d & -b \\ -c & a\\ \end{pmatrix}.


25 January 2009 at 11:19 am 2 comments