Fast and accurate ellipse detection is critical in certain computer vision tasks. In this paper, we propose an arc adjacency matrix-based ellipse detection (AAMED) method to fulfill this requirement. At first, after segmenting the edges into elliptic arcs, the digraph-based arc adjacency matrix (AAM) is constructed to describe their triple sequential adjacency states. Curvature and region constraints are employed to make the AAM sparse. Secondly, through bidirectionally searching the AAM, we can get all arc combinations which are probably true ellipse candidates. The cumulative-factor (CF) based cumulative matrices (CM) are worked out simultaneously. CF is irrelative to the image context and can be pre-calculated. CM is related to the arcs or arc combinations and can be calculated by the addition or subtraction of CF. Then the ellipses are efficiently fitted from these candidates through twice eigendecomposition of CM using Jacobi method. Finally, a comprehensive validation score is proposed to eliminate false ellipses effectively. The score is mainly influenced by the constraints about adaptive shape, tangent similarity, distribution compensation. Experiments show that our method outperforms the 12 state-of-the-art methods on 9 datasets as a whole, with reference to recall, precision, F-measure, and time-consumption.