Ben Burton has implemented Haken's algorithm in Regina. He (and Rubinstein and Tillman) have a functional algorithm to determine if a normal surface in a triangulated 3-manifold is (in)compressible. It's not terribly fast but it's fast enough to give a proof that the Seifert-Weber space does not contain an incompressible surface. This is a recent paper of theirs on the arXiv: http://front.math.ucdavis.edu/0909.4625

The main issue is that Haken's algorithm is extremely memory-intensive. If you run Haken's algorithm on the Rolfsen/Conway table of knots, the first thing you have to do is triangulate the knot complement. Efficient ideal triangulations are readily generated by the algorithm used in SnapPea (originally due to Thurston, as far as I know). But normal surface theory isn't totally happy with ideal triangulations so what Regina does is replace that triangulation with a semi-simplicial triangulation of a compact manifold (the complement of an open tubular neighbourhood of the knot). This makes the triangulation decidedly less efficient. I believe people like Burton, Jaco and Rubinstein are working on avoiding this step but it's not complete.

Anyhow, so you have to subdivide to get to a point where the normal surface theory is happy. Regina can run through the knot tables, applying the Haken algorithm to each knot. On my laptop it completes the knot table in about a day. So it's not terribly slow. But sometimes Regina is using 2 to 4Gb of RAM. And I believe this is largely normal surface enumeration that takes the bulk of the effort. I'll see if I can get Ben to comment.

Ben Burton has implemented Haken's algorithm in Regina. He (and Rubinstein and Tillman) have a functional algorithm to determine if a normal surface in a triangulated 3-manifold is (in)compressible. It's not terribly fast but it's fast enough to give a proof that the Seifert-Weber space does not contain an incompressible surface. This is a recent paper of theirs on the arXiv: https://arxiv.org/abs/0909.4625

The main issue is that Haken's algorithm is extremely memory-intensive. If you run Haken's algorithm on the Rolfsen/Conway table of knots, the first thing you have to do is triangulate the knot complement. Efficient ideal triangulations are readily generated by the algorithm used in SnapPea (originally due to Thurston, as far as I know). But normal surface theory isn't totally happy with ideal triangulations so what Regina does is replace that triangulation with a semi-simplicial triangulation of a compact manifold (the complement of an open tubular neighbourhood of the knot). This makes the triangulation decidedly less efficient. I believe people like Burton, Jaco and Rubinstein are working on avoiding this step but it's not complete.

Anyhow, so you have to subdivide to get to a point where the normal surface theory is happy. Regina can run through the knot tables, applying the Haken algorithm to each knot. On my laptop it completes the knot table in about a day. So it's not terribly slow. But sometimes Regina is using 2 to 4Gb of RAM. And I believe this is largely normal surface enumeration that takes the bulk of the effort. I'll see if I can get Ben to comment.

Ben Burton has implemented Haken's algorithm in Regina. He (and Rubinstein and Tillman) have a functional algorithm to determine if a normal surface in a triangulated 3-manifold is (in)compressible. It's not terribly fast but it's fast enough to give a proof that the Seifert-Weber space does not contain an incompressible surface. This is a recent paper of theirs on the arXiv: http://front.math.ucdavis.edu/0909.4625

The main issue is that Haken's algorithm is extremely memory-intensive. If you run Haken's algorithm on the Rolfsen/Conway table of knots, the first thing you have to do is triangulate the knot complement. Efficient ideal triangulations are readily generated by the algorithm used in SnapPea (originally due to Thurston, as far as I know). But normal surface theory isn't totally happy with ideal triangulations so what Regina does is replace that triangulation with a semi-simplicial triangulation of a compact manifold (the complement of an open tubular neighbourhood of the knot). This makes the triangulation decidedly less efficient. I believe people like Burton, Jaco and Rubinstein are working on avoiding this step but it's not complete.

Anyhow, so you have to subdivide to get to a point where the normal surface theory is happy. Regina can run through the knot tables, applying the Haken algorithm to each knot. On my laptop it completes the knot table in about a day. So it's not terribly slow. But sometimes the computer is using 2 to 4Gb of RAM. And I believe this is largely normal surface enumeration that takes the bulk of the effort. I'll see if I can get Ben to comment.

Ben Burton has implemented Haken's algorithm in Regina. He (and Rubinstein and Tillman) have a functional algorithm to determine if a normal surface in a triangulated 3-manifold is (in)compressible. It's not terribly fast but it's fast enough to give a proof that the Seifert-Weber space does not contain an incompressible surface. This is a recent paper of theirs on the arXiv: http://front.math.ucdavis.edu/0909.4625

The main issue is that Haken's algorithm is extremely memory-intensive. If you run Haken's algorithm on the Rolfsen/Conway table of knots, the first thing you have to do is triangulate the knot complement. Efficient ideal triangulations are readily generated by the algorithm used in SnapPea (originally due to Thurston, as far as I know). But normal surface theory isn't totally happy with ideal triangulations so what Regina does is replace that triangulation with a semi-simplicial triangulation of a compact manifold (the complement of an open tubular neighbourhood of the knot). This makes the triangulation decidedly less efficient. I believe people like Burton, Jaco and Rubinstein are working on avoiding this step but it's not complete.

Anyhow, so you have to subdivide to get to a point where the normal surface theory is happy. Regina can run through the knot tables, applying the Haken algorithm to each knot. On my laptop it completes the knot table in about a day. So it's not terribly slow. But sometimes Regina is using 2 to 4Gb of RAM. And I believe this is largely normal surface enumeration that takes the bulk of the effort. I'll see if I can get Ben to comment.