Title | **On the complexity of counting components of algebraic varieties** |

Author(s) | Peter Bürgisser, Peter Scheiblechner |

Type | Article in Journal |

Abstract | We give a uniform method for the two problems of counting the connected and irreducible components of complex algebraic varieties. Our algorithms are purely algebraic, i.e., they use only the field structure of C . They work in parallel polynomial time, i.e., they can be implemented by algebraic circuits of polynomial depth. The design of our algorithms relies on the concept of algebraic differential forms. A further important building block is an algorithm of Szántó computing a variant of characteristic sets. Furthermore, we use these methods to obtain a parallel polynomial time algorithm for computing the Hilbert polynomial of a projective variety which is arithmetically Cohen–Macaulay. |

Keywords | Characteristic sets, Complexity, Connected components, Differential forms, Irreducible components |

ISSN | 0747-7171 |

URL |
http://www.sciencedirect.com/science/article/pii/S0747717109000133 |

Language | English |

Journal | Journal of Symbolic Computation |

Volume | 44 |

Number | 9 |

Pages | 1114 - 1136 |

Year | 2009 |

Note | Effective Methods in Algebraic Geometry |

Edition | 0 |

Translation |
No |

Refereed |
No |