Are applications of group theory known to exist in numerical analysis? One particular aspect I am curious about is whether matrix groups have been successfully used to derive algorithms. Also, are there aspects of numerical analysis that would have been difficult to conceive or derive WITHOUT the help of group theory?
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
Alain Connes& K mentions some "Butcher group" ( http://arxiv.org/abs/hep-th/9904044 ):
... We emphasize the unifying role which the Butcher group, discovered in the study of numerical integration of ordinary differential equations, plays in QFT.
See also:
On the Hopf Algebraic Structure of Lie Group Integrators H. Z. Munthe-Kaas, W. M. Wright
Hopf algebras of formal diffeomorphisms and numerical integration on manifolds Alexander Lundervold, Hans Munthe-Kaas
Hopf algebras are in some sense "almost groups":) so hopefully this should qualify.
In general it seems to me that these series of works by Connes, Kreimer, Broadhurst, Moscovich & K on the Hopf algebras in various fields of math is quite fascinating...
answered Jul 25, 2012 at 11:54
$\begingroup$
$\endgroup$
2
There is a (recent) approach to the problem of fast matrix multiplication that involves representation theory of finite (nonabelian) groups. (Roughly, it reduces/transfers the problem of the existence of fast algorithms to certain question on representations of finite groups.) This was pioneered by Cohn and Umans, see for example Group theoretic algorithms for matrix multiplication by Cohn, Kleinberg, Szegedy, Umans for more details.
However, as incidentally recently mentioned on MO by one of the authors these algorithms are not / cannot (yet) be used in practise.
-
$\begingroup$ Well, if it's non-abelian, this must be group theory :) . $\endgroup$ Commented Jul 25, 2012 at 15:31
-
$\begingroup$ @Denis Serre: sure, that's why I included this information! :D More seriously, roughly but in more detail then the answer, the problem is the existence of a group having a triple of subsets with a certain propery such that the product of the cardinalities of these three sets exceeds the sum of the cubes of the degrees of the characters of this group (and related things). So the problem is really: does such a group exist?! So quite group-theory-ish. $\endgroup$– user9072Commented Jul 25, 2012 at 15:46
$\begingroup$
$\endgroup$
3
As far as DFT and FFT is considered as a part of Numerical Analysis, finite abelian groups apply, especially ${\mathbb Z}/2^n{\mathbb Z}$.
answered Jul 25, 2012 at 12:13
-
2$\begingroup$ Another question is whether finite abelian groups are 'group theory.' ;) $\endgroup$– user9072Commented Jul 25, 2012 at 12:48
-
1$\begingroup$ @quid. Perhaps you should ask an MO question :) . $\endgroup$ Commented Jul 25, 2012 at 13:11
-
2$\begingroup$ @Denis Serre: perhaps, but I am scared it will get closed as 'subjective and argumentative' :) $\endgroup$– user9072Commented Jul 25, 2012 at 13:18
$\begingroup$
$\endgroup$
3
I recommend P. Winternitz, Group Theory and Numerical Analysis, AMS, 2005.
From Google Books:
The Workshop on Group Theory and Numerical Analysis brought together scientists working in several different but related areas. The unifying theme was the application of group theory and geometrical methods to the solution of differential and difference equations. The emphasis was on the combination of analytical and numerical methods and also the use of symbolic computation.
Also, P.J. Oliver, Applications of Lie Groups to Differential Equations, Springer, 2000.
A solid introduction to applications of Lie groups to differential equations which have proved to be useful in practice. The computational methods are presented such that graduates and researchers can readily learn to use them.
-
1$\begingroup$ Not sure that Oliver's book mentions "numerical analysis" aspects of DE... $\endgroup$ Commented Jul 25, 2012 at 11:57
-
2$\begingroup$ there are also applications of Lie theory to finite difference equations (and in particular to difference schemes for DEs and PDEs). See e.g. "Applications of Lie Groups to Difference Equations" by Vladimir Dorodnitsyn (CRC Press 2010, amazon.com/…) $\endgroup$ Commented Jul 25, 2012 at 12:22
-
$\begingroup$ One might point out that the above mentioned author is not “Oliver” but Olver. $\endgroup$– LubinCommented Jan 12, 2013 at 21:23
$\begingroup$
$\endgroup$
To solve PDE exactly, you can use the "differential Galois theory" which first was studied by Sofus Lie and more recently by Ovsiannikov and his followers. See, for example Ovsyannikov, L. V. The group analysis purposes. Modern group analysis, V (Johannesburg, 1994). Lie Groups Appl. 1 (1994), no. 1, 193–202. I am sure that similar ideas can work in numerical analysis.
$\begingroup$
$\endgroup$
An example of ideas from Lie groups being used for the analysis of ODE integrators can be found in Reich, S. (1999). Backward error analysis for numerical integrators. SIAM Journal on Numerical Analysis, 36(5), 1549–1570..
