We present an algorithm, based on Newton’s method, for finding all roots of univariate complex polynomials so that the observed complexity is linear in the degree, up to logarithmic factors. Unlike the usual Newton method, which finds at most one root at a time, it is global in the sense that it attempts to find all roots of polynomials simultaneously.

We demonstrate the feasibility of this algorithm by employing it to find all roots of several families of polynomials of degrees up to more than one billion (10⁹). In all cases, the observed (empirical) complexity for finding all roots of a polynomial of degree d – measured either as the number of Newton iterations or computing time – was between O (dlnd) and O (dln³d), with small constants.

This thesis consists of three papers.

In Paper I, we identify the cohomology of the stable classifying space of homotopy automorphisms (relative to an embedded disk) of connected sums of S^k × S^l, where 3 ≤ k < l ≤ 2k - 2. We express the result in terms of Lie graph complex homology.

In Paper II, we construct a rational model for the classifying space Baut_A(X) of homotopy automorphisms of a simply connected finite CW-complex X relative to a simply connected subcomplex A. Using this model, we provide a purely algebraic description of the cohomology of this classifying space. This constitutes an important input for the results of Paper I.

In Paper III, we show that modular operads are equivalent to modules over a certain simple properad which we call the Brauer properad. Furthermore we show that the Feynman transform corresponds to the cobar construction for modules of this kind. To make this precise, we extend the machinery of the bar and cobar constructions relative to a twisting morphism to modules over a general properad. As an application, we provide the foundations of a Koszul duality theory for modular operads.

We identify the cohomology of the stable classifying space of homotopy automorphisms (relative to an embedded disk) of connected sums of S^k×S^l, where 3≤k<l≤2k−2. The result is expressed in terms of Lie graph complex homology.

We show that modular operads are equivalent to modules over a certain simple properad which we call the Brauer properad. Furthermore, we show that, in this setting, the Feynman transform corresponds to the cobar construction for modules of this kind. To make this precise, we extend the machinery of the bar and cobar constructions relative to a twisting morphism to modules over a general properad. This generalizes the classical case of algebras over an operad and might be of independent interest. As an application, we sketch a Koszul duality theory for modular operads.