Kernighan–Lin algorithm

2013-11-25T15:56:26Z

108.56.236.116: /* Pseudocode */

{{cleanup|date = June 2009}}

In [[algebraic geometry]], a '''conic bundle''' is an [[algebraic variety]] that appears as a solution of a Cartesian equation of the form

: <math>X^2 + aXY + b Y^2 = P (T).\,</math>

Theoretically, it can be considered as a [[Severi–Brauer surface]], or more precisely as a [[Châtelet surface]]. This can be a double covering of a [[ruled surface]]. Through an isomorphism, it can be associated with a symbol <math>(a, P)</math> in the second [[Galois cohomology]] of the field <math>k</math>.

In fact, it is a surface with a well-understood [[divisor class group]] and simplest cases share with [[Del Pezzo surface]]s the property of being a [[rational surface]]. But many problems of contemporary mathematics remain open, notably (for those examples which are not rational) the question of [[unirationality]].

== A naive point of view ==

To write correctly a conic bundle, one must first reduce the [[quadratic form]] of the left hand side. Thus, after a harmless change, it has a simple expression like

: <math> X^2 - aY^2 = P (T). \, </math>

In a second step, it should be placed in a [[projective space]] in order to complete the surface "at infinity".

To do this, we write the equation in [[homogeneous coordinates]] and expresses the first visible part of the fiber

: <math> X^2 - aY^2 = P (T) Z^2. \, </math>

That is not enough to complete the fiber as non-singular (clean and smooth), and then glue it to infinity by a change of classical maps:

Seen from infinity, (i.e. through the change <math> T\mapsto T'=\frac 1 T</math>), the same fiber (excepted the fibers <math>T = 0</math> and <math>T '= 0</math>), written as the set of solutions <math>X'^2 - aY'^2= P^* (T') Z'^2 </math> where <math>P^* (T ')</math> appears naturally as the [[reciprocal polynomial]] of <math>P</math>. Details are below about the map-change <math>[x ':y': z ']</math>.

== The fiber ''c'' ==

Going a little further, while simplifying the issue, limit to cases where the field <math>k</math> is of [[characteristic zero]] and denote by <math>m</math> any integer except zero. Denote by ''P''(''T'') a polynomial with coefficients in the field <math>k</math>, of degree 2''m'' or 2''m'' − 1, without multiple root. Consider the scalar ''a''.

One defines the reciprocal polynomial by <math>P^*(T')=T^{2m}P(\frac 1 T)</math>, and the conic bundle ''F''''a'',''P'' as follows :

;Definition:

<math>F_{a,P}</math> is the surface obtained as "gluing" of the two surfaces <math>U</math> and <math>U'</math> of equations

:<math> X^2 - aY^ 2 = P (T) Z^2</math>

and

:<math>X '^2 - Y'^2 = P (T ') Z'^ 2</math>

along the open sets by isomorphisms

:<math>x '= x,, y' = y, </math> and <math>z '= z t^m</math>.

One shows the following result :

;Fundamental property:

The surface ''F''''a'',''P'' is a ''k'' clean and smooth surface, the mapping defined by

:<math>p: U \to P_{1, k}</math>

by

:<math>([x:y:z],t)\mapsto t</math>

and the same on <math> U '</math> gives to ''F''''a'',''P'' a structure of conic bundle over ''P''1,''k''.

== See also ==
* [[Algebraic surface]]
* [[Intersection number (algebraic geometry)]]
* [[List of complex and algebraic surfaces]]

==References==
*{{cite book
| author = [[Robin Hartshorne]]
| year = 1977
| title = Algebraic Geometry
| publisher = [[Springer Science+Business Media|Springer-Verlag]]
| isbn = 0-387-90244-9
}}
*{{cite book
| author = [[David Cox]]
| coauthors = John Little, Don O'Shea
| year = 1997
| title = Ideals, Varieties, and Algorithms
| edition = second edition
| publisher = [[Springer Science+Business Media|Springer-Verlag]]
| isbn = 0-387-94680-2
}}
*{{cite book
| author = [[David Eisenbud]]
| year = 1999
| title = Commutative Algebra with a View Toward Algebraic Geometry
| publisher = [[Springer Science+Business Media|Springer-Verlag]]
| isbn = 0-387-94269-6
}}

[[Category:Algebraic geometry]]
[[Category:Algebraic varieties]]

formulasearchengine - User contributions [en]

Kernighan–Lin algorithm