Abstract

We present what we believe to be a new algorithm, FRactal Iterative Method (FRiM), aiming at the reconstruction of the optical wavefront from measurements provided by a wavefront sensor. As our application is adaptive optics on extremely large telescopes, our algorithm was designed with speed and best quality in mind. The latter is achieved thanks to a regularization that enforces prior statistics. To solve the regularized problem, we use the conjugate gradient method, which takes advantage of the sparsity of the wavefront sensor model matrix and avoids the storage and inversion of a huge matrix. The prior covariance matrix is, however, non-sparse, and we derive a fractal approximation to the Karhunen–Loève basis thanks to which the regularization by Kolmogorov statistics can be computed in O(N) operations, with N being the number of phase samples to estimate. Finally, we propose an effective preconditioning that also scales as O(N) and yields the solution in five to ten conjugate gradient iterations for any N. The resulting algorithm is therefore O(N). As an example, for a 128×128 Shack–Hartmann wavefront sensor, the FRiM appears to be more than 100 times faster than the classical vector-matrix multiplication method.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. F. Roddier, Adaptive Optics in Astronomy (Cambridge U. Press, 1999).
    [CrossRef]
  2. E. Gendron and P. Léna, “Astronomical adaptive optics. I. Modal control optimization,” Astron. Astrophys.  291, 337–347 (1994).
  3. M. Le Louarn, N. Hubin, M. Sarazin, and A. Tokovinin, “New challenges for adaptive optics: extremely large telescopes,” Mon. Not. R. Astron. Soc.  317, 535–544 (2000).
    [CrossRef]
  4. N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.
  5. L. A. Poyneer, D. T. Gavel, and J. M. Brase, “Fast wave-front reconstruction in large adaptive optics systems with use of the Fourier transform,” J. Opt. Soc. Am. A  19, 2100–2111 (2002).
    [CrossRef]
  6. L. A. Poyneer, D. Dillon, S. Thomas, and B. A. Macintosh, “Laboratory demonstration of accurate and efficient nanometer-level wavefront control for extreme adaptive optics,” Appl. Opt.  47, 1317–1326 (2008).
    [CrossRef] [PubMed]
  7. D. G. MacMartin, “Local, hierarchic, and iterative reconstructors for adaptive optics,” J. Opt. Soc. Am. A  20, 1084–1093 (2003).
    [CrossRef]
  8. B. Le Roux, J.-M. Conan, C. Kulcsár, H.-F. Raynaud, L. M. Mugnier, and T. Fusco, “Optimal control law for classical and multiconjugate adaptive optics,” J. Opt. Soc. Am. A  21, 1261–1276 (2004).
    [CrossRef]
  9. B. L. Ellerbroek, “Efficient computation of minimum-variance wave-front reconstructors with sparse matrix techniques,” J. Opt. Soc. Am. A  19, 1803–1816 (2002).
    [CrossRef]
  10. C. R. Vogel, “Sparse matrix methods for wavefront reconstruction revisited,” Proc. SPIE  5490, 1327–1335 (2004).
    [CrossRef]
  11. W. H. Southwell, “Wave-front estimation from wave-front slope measurements,” J. Opt. Soc. Am.  70, 998–1006 (1980).
    [CrossRef]
  12. J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed. (Springer Verlag, 2006).
  13. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, 1992).
  14. W. J. Wild, E. J. Kibblewhite, and R. Vuilleumier, “Sparse matrix wave-front estimators for adaptive-optics systems for large ground-based telescopes,” Opt. Lett.  20, 955–957 (1995).
    [CrossRef] [PubMed]
  15. R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
    [CrossRef]
  16. L. Gilles, C. R. Vogel, and B. L. Ellerbroek, “Multigrid preconditioned conjugate-gradient method for large-scale wave-front reconstruction,” J. Opt. Soc. Am. A  19, 1817–1822 (2002).
    [CrossRef]
  17. L. Gilles, “Order-N sparse minimum-variance open-loop reconstructor for extreme adaptive optics,” Opt. Lett.  28, 1927–1929 (2003).
    [CrossRef] [PubMed]
  18. L. Gilles, B. L. Ellerbroek, and C. R. Vogel, “Preconditioned conjugate gradient wave-front reconstructors for multiconjugate adaptive optics,” Appl. Opt.  42, 5233–5250 (2003).
    [CrossRef] [PubMed]
  19. Q. Yang, C. R. Vogel, and B. L. Ellerbroek, “Fourier domain preconditioned conjugate gradient algorithm for atmospheric tomography,” Appl. Opt.  45, 5281–5293 (2006).
    [CrossRef] [PubMed]
  20. C. R. Vogel and Q. Yang, “Fast optimal wavefront reconstruction for multi-conjugate adaptive optics using the Fourier domain preconditioned conjugate gradient algorithm,” Opt. Express  14, 7487–7498 (2006).
    [CrossRef] [PubMed]
  21. L. Gilles, B. Ellerbroek, and C. Vogel, “A comparison of multigrid V-cycle versus Fourier domain preconditioning for laser guide star atmospheric tomography,” in Signal Recovery and Synthesis, OSA Topical Meetings, B.L.Ellerbroek and J.C.Christou, eds. (Optical Society of America, 2007), paper JTuA1.
  22. L. Gilles and B. L. Ellerbroek, “Split atmospheric tomography using laser and natural guide stars,” J. Opt. Soc. Am. A  25, 2427–2435 (2008).
    [CrossRef]
  23. R. G. Lane, A. Glindemann, and J. C. Dainty, “Simulation of a Kolmogorov phase screen,” Waves Random Media  2, 209–224 (1992).
    [CrossRef]
  24. D. L. Fried, “Least-squares fitting a wave-front distortion estimate to an array of phase-difference measurements,” J. Opt. Soc. Am.  67, 370–375 (1977).
    [CrossRef]
  25. E. Thiébaut, “Introduction to image reconstruction and inverse problems,” in NATO Science Series II., Mathematics, Physics and Chemistry, Vol. 198,R.Foy and F.-C.Foy, eds. (Springer, 2005), p. 397.
  26. J. Herrmann, “Phase variance and Strehl ratio in adaptive optics,” J. Opt. Soc. Am. A  9, 2257–2258 (1992).
    [CrossRef]
  27. A. Tarantola, Inverse Problem Theory and Methods for Model Parameter Estimation (SIAM, 2005).
    [CrossRef]
  28. A. Tarantola and B. Valette, “Inverse problems = quest for information for information,” J. Geophys.  50, 159–170 (1982).
  29. D. L. Fried, “Statistics of a geometric representation of wavefront distortion,” J. Opt. Soc. Am.  55, 1427–1435 (1965).
    [CrossRef]
  30. G. Rousset, “Wavefront sensing,” in Adaptive Optics for Astronomy, Vol.  423 of Proceedings of NATO ASI Series C, D.M.Alloin and J.-M.Mariotti, eds. (Kluwer, 1993), pp. 115–137.
  31. N. Roddier, “Atmospheric wavefront simulation using zernike polynomials,” Opt. Eng. (Bellingham)  29, 1174–1180 (1990).
    [CrossRef]
  32. J. Skilling and R. K. Bryan, “Maximum entropy image reconstruction: general algorithm,” Mon. Not. R. Astron. Soc.  211, 111–124 (1984).
  33. C. Béchet, M. Tallon, and E. Thiébaut, “Comparison of minimum-norm maximum likelihood and maximum a posteriori wavefront reconstructions for large adaptive optics systems,” J. Opt. Soc. Am. A  26, 497–508 (2009).
    [CrossRef]
  34. C. Béchet, “Commande optimale rapide pour l’optique adaptative des futurs télescopes hectométriques,” Ph.D. dissertation (Ecole Centrale de Lyon, 2008).
  35. C. Béchet, M. Tallon, and E. Thiébaut, “FRIM: minimum-variance reconstructor with a fractal iterative method,” in Advances in Adaptive Optics II, Vol.  6272 of SPIE Conference, D.B. C. B. L.Ellerbroek, ed. (2006), p. 62722U.
  36. C. Béchet, M. Tallon, and E. Thiébaut, “Closed-loop AO performance with FrIM,” in Adaptive Optics: Analysis and Methods, Conference of the Optical Society of America (Optical Society of America, 2007), paper JTuA4.
  37. D. Munro, Yorick,http://yorick.sourceforge.net/http://yorick.sourceforge.net/.

2009 (1)

2008 (3)

2007 (2)

L. Gilles, B. Ellerbroek, and C. Vogel, “A comparison of multigrid V-cycle versus Fourier domain preconditioning for laser guide star atmospheric tomography,” in Signal Recovery and Synthesis, OSA Topical Meetings, B.L.Ellerbroek and J.C.Christou, eds. (Optical Society of America, 2007), paper JTuA1.

C. Béchet, M. Tallon, and E. Thiébaut, “Closed-loop AO performance with FrIM,” in Adaptive Optics: Analysis and Methods, Conference of the Optical Society of America (Optical Society of America, 2007), paper JTuA4.

2006 (4)

C. Béchet, M. Tallon, and E. Thiébaut, “FRIM: minimum-variance reconstructor with a fractal iterative method,” in Advances in Adaptive Optics II, Vol.  6272 of SPIE Conference, D.B. C. B. L.Ellerbroek, ed. (2006), p. 62722U.

Q. Yang, C. R. Vogel, and B. L. Ellerbroek, “Fourier domain preconditioned conjugate gradient algorithm for atmospheric tomography,” Appl. Opt.  45, 5281–5293 (2006).
[CrossRef] [PubMed]

C. R. Vogel and Q. Yang, “Fast optimal wavefront reconstruction for multi-conjugate adaptive optics using the Fourier domain preconditioned conjugate gradient algorithm,” Opt. Express  14, 7487–7498 (2006).
[CrossRef] [PubMed]

J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed. (Springer Verlag, 2006).

2005 (3)

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

E. Thiébaut, “Introduction to image reconstruction and inverse problems,” in NATO Science Series II., Mathematics, Physics and Chemistry, Vol. 198,R.Foy and F.-C.Foy, eds. (Springer, 2005), p. 397.

A. Tarantola, Inverse Problem Theory and Methods for Model Parameter Estimation (SIAM, 2005).
[CrossRef]

2004 (2)

2003 (3)

2002 (3)

2000 (1)

M. Le Louarn, N. Hubin, M. Sarazin, and A. Tokovinin, “New challenges for adaptive optics: extremely large telescopes,” Mon. Not. R. Astron. Soc.  317, 535–544 (2000).
[CrossRef]

1999 (1)

F. Roddier, Adaptive Optics in Astronomy (Cambridge U. Press, 1999).
[CrossRef]

1995 (1)

1994 (2)

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

E. Gendron and P. Léna, “Astronomical adaptive optics. I. Modal control optimization,” Astron. Astrophys.  291, 337–347 (1994).

1993 (1)

G. Rousset, “Wavefront sensing,” in Adaptive Optics for Astronomy, Vol.  423 of Proceedings of NATO ASI Series C, D.M.Alloin and J.-M.Mariotti, eds. (Kluwer, 1993), pp. 115–137.

1992 (3)

J. Herrmann, “Phase variance and Strehl ratio in adaptive optics,” J. Opt. Soc. Am. A  9, 2257–2258 (1992).
[CrossRef]

R. G. Lane, A. Glindemann, and J. C. Dainty, “Simulation of a Kolmogorov phase screen,” Waves Random Media  2, 209–224 (1992).
[CrossRef]

W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, 1992).

1990 (1)

N. Roddier, “Atmospheric wavefront simulation using zernike polynomials,” Opt. Eng. (Bellingham)  29, 1174–1180 (1990).
[CrossRef]

1984 (1)

J. Skilling and R. K. Bryan, “Maximum entropy image reconstruction: general algorithm,” Mon. Not. R. Astron. Soc.  211, 111–124 (1984).

1982 (1)

A. Tarantola and B. Valette, “Inverse problems = quest for information for information,” J. Geophys.  50, 159–170 (1982).

1980 (1)

1977 (1)

1965 (1)

Arsenault, R.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

Barrett, R.

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

Béchet, C.

C. Béchet, M. Tallon, and E. Thiébaut, “Comparison of minimum-norm maximum likelihood and maximum a posteriori wavefront reconstructions for large adaptive optics systems,” J. Opt. Soc. Am. A  26, 497–508 (2009).
[CrossRef]

C. Béchet, “Commande optimale rapide pour l’optique adaptative des futurs télescopes hectométriques,” Ph.D. dissertation (Ecole Centrale de Lyon, 2008).

C. Béchet, M. Tallon, and E. Thiébaut, “Closed-loop AO performance with FrIM,” in Adaptive Optics: Analysis and Methods, Conference of the Optical Society of America (Optical Society of America, 2007), paper JTuA4.

C. Béchet, M. Tallon, and E. Thiébaut, “FRIM: minimum-variance reconstructor with a fractal iterative method,” in Advances in Adaptive Optics II, Vol.  6272 of SPIE Conference, D.B. C. B. L.Ellerbroek, ed. (2006), p. 62722U.

Berry, M.

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

Brase, J. M.

Bryan, R. K.

J. Skilling and R. K. Bryan, “Maximum entropy image reconstruction: general algorithm,” Mon. Not. R. Astron. Soc.  211, 111–124 (1984).

Chan, T. F.

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

Clare, R. M.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

Conan, J. -M.

Dainty, J. C.

R. G. Lane, A. Glindemann, and J. C. Dainty, “Simulation of a Kolmogorov phase screen,” Waves Random Media  2, 209–224 (1992).
[CrossRef]

Dekany, R.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

Demmel, J.

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

der Vorst, H. V.

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

Dillon, D.

Donato, J.

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

Dongarra, J.

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

Eijkhout, V.

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

Ellerbroek, B.

L. Gilles, B. Ellerbroek, and C. Vogel, “A comparison of multigrid V-cycle versus Fourier domain preconditioning for laser guide star atmospheric tomography,” in Signal Recovery and Synthesis, OSA Topical Meetings, B.L.Ellerbroek and J.C.Christou, eds. (Optical Society of America, 2007), paper JTuA1.

Ellerbroek, B. L.

Flannery, B. P.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, 1992).

Fried, D. L.

Fusco, T.

Gavel, D. T.

Gendron, E.

E. Gendron and P. Léna, “Astronomical adaptive optics. I. Modal control optimization,” Astron. Astrophys.  291, 337–347 (1994).

Gilles, L.

L. Gilles and B. L. Ellerbroek, “Split atmospheric tomography using laser and natural guide stars,” J. Opt. Soc. Am. A  25, 2427–2435 (2008).
[CrossRef]

L. Gilles, B. Ellerbroek, and C. Vogel, “A comparison of multigrid V-cycle versus Fourier domain preconditioning for laser guide star atmospheric tomography,” in Signal Recovery and Synthesis, OSA Topical Meetings, B.L.Ellerbroek and J.C.Christou, eds. (Optical Society of America, 2007), paper JTuA1.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

L. Gilles, “Order-N sparse minimum-variance open-loop reconstructor for extreme adaptive optics,” Opt. Lett.  28, 1927–1929 (2003).
[CrossRef] [PubMed]

L. Gilles, B. L. Ellerbroek, and C. R. Vogel, “Preconditioned conjugate gradient wave-front reconstructors for multiconjugate adaptive optics,” Appl. Opt.  42, 5233–5250 (2003).
[CrossRef] [PubMed]

L. Gilles, C. R. Vogel, and B. L. Ellerbroek, “Multigrid preconditioned conjugate-gradient method for large-scale wave-front reconstruction,” J. Opt. Soc. Am. A  19, 1817–1822 (2002).
[CrossRef]

Glindemann, A.

R. G. Lane, A. Glindemann, and J. C. Dainty, “Simulation of a Kolmogorov phase screen,” Waves Random Media  2, 209–224 (1992).
[CrossRef]

Herriot, G.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

Herrmann, J.

Hubin, N.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

M. Le Louarn, N. Hubin, M. Sarazin, and A. Tokovinin, “New challenges for adaptive optics: extremely large telescopes,” Mon. Not. R. Astron. Soc.  317, 535–544 (2000).
[CrossRef]

Kasper, M.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

Kibblewhite, E. J.

Kulcsár, C.

Lane, R. G.

R. G. Lane, A. Glindemann, and J. C. Dainty, “Simulation of a Kolmogorov phase screen,” Waves Random Media  2, 209–224 (1992).
[CrossRef]

Le Louarn, M.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

M. Le Louarn, N. Hubin, M. Sarazin, and A. Tokovinin, “New challenges for adaptive optics: extremely large telescopes,” Mon. Not. R. Astron. Soc.  317, 535–544 (2000).
[CrossRef]

Le Roux, B.

Léna, P.

E. Gendron and P. Léna, “Astronomical adaptive optics. I. Modal control optimization,” Astron. Astrophys.  291, 337–347 (1994).

Macintosh, B. A.

MacMartin, D. G.

Marchetti, E.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

Mugnier, L. M.

Munro, D.

D. Munro, Yorick,http://yorick.sourceforge.net/http://yorick.sourceforge.net/.

Nocedal, J.

J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed. (Springer Verlag, 2006).

Oberti, S.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

Poyneer, L. A.

Pozo, R.

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

Press, W. H.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, 1992).

Raynaud, H. -F.

Roddier, F.

F. Roddier, Adaptive Optics in Astronomy (Cambridge U. Press, 1999).
[CrossRef]

Roddier, N.

N. Roddier, “Atmospheric wavefront simulation using zernike polynomials,” Opt. Eng. (Bellingham)  29, 1174–1180 (1990).
[CrossRef]

Romine, C.

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

Rousset, G.

G. Rousset, “Wavefront sensing,” in Adaptive Optics for Astronomy, Vol.  423 of Proceedings of NATO ASI Series C, D.M.Alloin and J.-M.Mariotti, eds. (Kluwer, 1993), pp. 115–137.

Sarazin, M.

M. Le Louarn, N. Hubin, M. Sarazin, and A. Tokovinin, “New challenges for adaptive optics: extremely large telescopes,” Mon. Not. R. Astron. Soc.  317, 535–544 (2000).
[CrossRef]

Skilling, J.

J. Skilling and R. K. Bryan, “Maximum entropy image reconstruction: general algorithm,” Mon. Not. R. Astron. Soc.  211, 111–124 (1984).

Southwell, W. H.

Stoesz, J.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

Tallon, M.

C. Béchet, M. Tallon, and E. Thiébaut, “Comparison of minimum-norm maximum likelihood and maximum a posteriori wavefront reconstructions for large adaptive optics systems,” J. Opt. Soc. Am. A  26, 497–508 (2009).
[CrossRef]

C. Béchet, M. Tallon, and E. Thiébaut, “Closed-loop AO performance with FrIM,” in Adaptive Optics: Analysis and Methods, Conference of the Optical Society of America (Optical Society of America, 2007), paper JTuA4.

C. Béchet, M. Tallon, and E. Thiébaut, “FRIM: minimum-variance reconstructor with a fractal iterative method,” in Advances in Adaptive Optics II, Vol.  6272 of SPIE Conference, D.B. C. B. L.Ellerbroek, ed. (2006), p. 62722U.

Tarantola, A.

A. Tarantola, Inverse Problem Theory and Methods for Model Parameter Estimation (SIAM, 2005).
[CrossRef]

A. Tarantola and B. Valette, “Inverse problems = quest for information for information,” J. Geophys.  50, 159–170 (1982).

Teukolsky, S. A.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, 1992).

Thiébaut, E.

C. Béchet, M. Tallon, and E. Thiébaut, “Comparison of minimum-norm maximum likelihood and maximum a posteriori wavefront reconstructions for large adaptive optics systems,” J. Opt. Soc. Am. A  26, 497–508 (2009).
[CrossRef]

C. Béchet, M. Tallon, and E. Thiébaut, “Closed-loop AO performance with FrIM,” in Adaptive Optics: Analysis and Methods, Conference of the Optical Society of America (Optical Society of America, 2007), paper JTuA4.

C. Béchet, M. Tallon, and E. Thiébaut, “FRIM: minimum-variance reconstructor with a fractal iterative method,” in Advances in Adaptive Optics II, Vol.  6272 of SPIE Conference, D.B. C. B. L.Ellerbroek, ed. (2006), p. 62722U.

E. Thiébaut, “Introduction to image reconstruction and inverse problems,” in NATO Science Series II., Mathematics, Physics and Chemistry, Vol. 198,R.Foy and F.-C.Foy, eds. (Springer, 2005), p. 397.

Thomas, S.

Tokovinin, A.

M. Le Louarn, N. Hubin, M. Sarazin, and A. Tokovinin, “New challenges for adaptive optics: extremely large telescopes,” Mon. Not. R. Astron. Soc.  317, 535–544 (2000).
[CrossRef]

Valette, B.

A. Tarantola and B. Valette, “Inverse problems = quest for information for information,” J. Geophys.  50, 159–170 (1982).

Véran, J. -P.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

Vérinaud, C.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

Vetterling, W. T.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, 1992).

Vogel, C.

L. Gilles, B. Ellerbroek, and C. Vogel, “A comparison of multigrid V-cycle versus Fourier domain preconditioning for laser guide star atmospheric tomography,” in Signal Recovery and Synthesis, OSA Topical Meetings, B.L.Ellerbroek and J.C.Christou, eds. (Optical Society of America, 2007), paper JTuA1.

Vogel, C. R.

Vuilleumier, R.

Wild, W. J.

Wright, S. J.

J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed. (Springer Verlag, 2006).

Yang, Q.

Appl. Opt. (3)

Astron. Astrophys. (1)

E. Gendron and P. Léna, “Astronomical adaptive optics. I. Modal control optimization,” Astron. Astrophys.  291, 337–347 (1994).

J. Geophys. (1)

A. Tarantola and B. Valette, “Inverse problems = quest for information for information,” J. Geophys.  50, 159–170 (1982).

J. Opt. Soc. Am. (3)

J. Opt. Soc. Am. A (8)

Mon. Not. R. Astron. Soc. (2)

J. Skilling and R. K. Bryan, “Maximum entropy image reconstruction: general algorithm,” Mon. Not. R. Astron. Soc.  211, 111–124 (1984).

M. Le Louarn, N. Hubin, M. Sarazin, and A. Tokovinin, “New challenges for adaptive optics: extremely large telescopes,” Mon. Not. R. Astron. Soc.  317, 535–544 (2000).
[CrossRef]

Opt. Eng. (Bellingham) (1)

N. Roddier, “Atmospheric wavefront simulation using zernike polynomials,” Opt. Eng. (Bellingham)  29, 1174–1180 (1990).
[CrossRef]

Opt. Express (1)

Opt. Lett. (2)

Proc. SPIE (1)

C. R. Vogel, “Sparse matrix methods for wavefront reconstruction revisited,” Proc. SPIE  5490, 1327–1335 (2004).
[CrossRef]

Waves Random Media (1)

R. G. Lane, A. Glindemann, and J. C. Dainty, “Simulation of a Kolmogorov phase screen,” Waves Random Media  2, 209–224 (1992).
[CrossRef]

Other (13)

A. Tarantola, Inverse Problem Theory and Methods for Model Parameter Estimation (SIAM, 2005).
[CrossRef]

E. Thiébaut, “Introduction to image reconstruction and inverse problems,” in NATO Science Series II., Mathematics, Physics and Chemistry, Vol. 198,R.Foy and F.-C.Foy, eds. (Springer, 2005), p. 397.

G. Rousset, “Wavefront sensing,” in Adaptive Optics for Astronomy, Vol.  423 of Proceedings of NATO ASI Series C, D.M.Alloin and J.-M.Mariotti, eds. (Kluwer, 1993), pp. 115–137.

C. Béchet, “Commande optimale rapide pour l’optique adaptative des futurs télescopes hectométriques,” Ph.D. dissertation (Ecole Centrale de Lyon, 2008).

C. Béchet, M. Tallon, and E. Thiébaut, “FRIM: minimum-variance reconstructor with a fractal iterative method,” in Advances in Adaptive Optics II, Vol.  6272 of SPIE Conference, D.B. C. B. L.Ellerbroek, ed. (2006), p. 62722U.

C. Béchet, M. Tallon, and E. Thiébaut, “Closed-loop AO performance with FrIM,” in Adaptive Optics: Analysis and Methods, Conference of the Optical Society of America (Optical Society of America, 2007), paper JTuA4.

D. Munro, Yorick,http://yorick.sourceforge.net/http://yorick.sourceforge.net/.

N. Hubin, B. L. Ellerbroek, R. Arsenault, R. M. Clare, R. Dekany, L. Gilles, M. Kasper, G. Herriot, M. Le Louarn, E. Marchetti, S. Oberti, J. Stoesz, J.-P. Véran, and C. Vérinaud, “Adaptive optics for extremely large telescopes,” in Scientific Requirements for Extremely Large Telescopes, Vol.  232 of IAU Symposium, P.A.Whitelock, M.Dennefeld, and B.Leibundgut, eds. (Cambridge U. Press, 2005), pp. 60–85.

F. Roddier, Adaptive Optics in Astronomy (Cambridge U. Press, 1999).
[CrossRef]

R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, 1994).
[CrossRef]

J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed. (Springer Verlag, 2006).

W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, 1992).

L. Gilles, B. Ellerbroek, and C. Vogel, “A comparison of multigrid V-cycle versus Fourier domain preconditioning for laser guide star atmospheric tomography,” in Signal Recovery and Synthesis, OSA Topical Meetings, B.L.Ellerbroek and J.C.Christou, eds. (Optical Society of America, 2007), paper JTuA1.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (13)

Fig. 1
Fig. 1

PCG algorithm for solving A x = b , where A is a symmetric positive definite matrix and M is a preconditioner. The unpreconditioned version of the algorithm is simply obtained by taking M = I ; hence z k = r k .

Fig. 2
Fig. 2

Wavefront sensor with Fried geometry as used for our simulations. The black circles stand for phase samples w ( x , y ) , at the corners of the square subapertures of size a. This model is exact if we assume that the wavefront at any point in the pupil is obtained from a bilinear interpolation of phase samples at the corner of the subapertures.

Fig. 3
Fig. 3

The four initial values for wavefront generation, at the corners of the support.

Fig. 4
Fig. 4

Wavefront refinement. To generate a grid with cell size r / 2 , new values (in gray) are generated from wavefront values (in white) of a grid with cell size equal to r. Top left: new value from four values r / 2 apart. Top right: new edge value from three values r / 2 apart. Bottom: new value from four values r / 2 apart.

Fig. 5
Fig. 5

Structure function. Left: 2D isocontours; right: one-dimensional profile computed by radial averaging. Solid lines: Kolmogorov law 6.88 × ( r / r 0 ) 5 / 3 ; dotted lines: average of 1000 structure functions generated with the mid-point method.

Fig. 6
Fig. 6

Phase error as a function of the number of operations. Curves are the median value of 100 simulations with D / r 0 = 65 , σ noise = 1   rad / subaperture and r 0 has the same size as one subaperture. Solid curves are for CG, dashed curves are for PCG with Jacobi preconditioner, and dotted curves are for PCG with optimal diagonal preconditioner. Thin curves are for (P)CG onto the wavefront samples w , whereas thick curves are for (P)CG onto the wavefront generator u .

Fig. 7
Fig. 7

Same as Fig. 6 but for σ noise = 0.5   rad / subaperture .

Fig. 8
Fig. 8

Same as Fig. 6 but for σ noise = 0.1   rad / subaperture .

Fig. 9
Fig. 9

Same as Fig. 6 but for σ noise = 0.05   rad / subaperture .

Fig. 10
Fig. 10

Same as Fig. 6 but for D / r 0 = 257 and σ noise = 1   rad / subaperture .

Fig. 11
Fig. 11

Same as Fig. 6 but for D / r 0 = 257 and σ noise = 0.5   rad / subaperture .

Fig. 12
Fig. 12

Decrease in the residual phase variance as a function of the number of iterations when using u as unknowns and optimal diagonal preconditioner. Each curve is the median value of 100 simulations. Three sets of curves are plotted for different values of σ noise 2 : 1 (solid), 0.09 (dashed), and 0.01 (dotted) rad 2 / r 0 . In each set of curves, the size of the system increases from bottom to top: 32, 64, 128, and 256 subapertures along the diameter of the pupil. Levels of Strehl ratios are indicated. The curves show that five to ten iterations are enough in most cases for a full reconstruction.

Fig. 13
Fig. 13

The same curves as those in Fig. 12 are plotted here, normalized by the initial variance of the phase. This shows a high relative attenuation ( 1 / 40 ) after the first iteration, in any configuration. In each set of curves: σ noise 2 = 1 (solid), 0.09 (dashed), and 0.01 (dotted) rad 2 / r 0 , the size of the system increases from top to bottom: 32, 64, 128, and 256 subapertures along the diameter of the pupil.

Tables (1)

Tables Icon

Table 1 Number of Operations Involved in CG and PCGs Applied to the Wavefront Restoration Problem Solved by Our Algorithm a

Equations (82)

Equations on this page are rendered with MathJax. Learn more.

d = S w + n ,
w ̃ = def R d ,
SR exp ( 1 A pupil [ w ̃ ( r ) w ( r ) ] 2 d r ) ,
R = arg   min R R d w 2 .
R = C w S T ( S C w S T + C n ) 1 ,
S T C n 1 S C w S T + S T = S T C n 1 ( S C w S T + C n ) = ( S T C n 1 S + C w 1 ) C w S T ,
R = ( S T C n 1 S + C w 1 ) 1 S T C n 1 ,
w = def R d = ( S T C n 1 S + C w 1 ) 1 S T C n 1 d ,
w = arg   min w { ( S w d ) T C n 1 ( S w d ) + w T C w 1 w } ,
( S T C n 1 S + C w 1 ) w = S T C n 1 d ,
A x = b ,
A = S T C n 1 S + C w 1
b = S T C n 1 d
d x ( x , y ) = 1 2 [ w ( x + a , y + a ) + w ( x + a , y ) w ( x , y + a ) w ( x , y ) ] ,
d y ( x , y ) = 1 2 [ w ( x + a , y + a ) w ( x + a , y ) + w ( x , y + a ) w ( x , y ) ] ,
C n diag ( Var ( n ) ) ,
C w = K K T ,
u = def K 1 w .
C u = u u T = K 1 w w T K T = K 1 C w K T = I ,
w T C w 1 w = w T K T K 1 w = K 1 w 2 2 = u 2 2 .
K = K 1 K 2 K p ,
[ w ( r i ) w ( r j ) ] 2 = f ( | r i r j | ) ,
f ( r ) = 6.88 × ( r / r 0 ) 5 / 3 ,
C i , j = w i w j = 1 2 ( σ i 2 + σ j 2 f i , j ) ,
C out = ( c 0 c 1 c 2 c 1 c 1 c 0 c 1 c 2 c 2 c 1 c 0 c 1 c 1 c 2 c 1 c 0 ) ,     with   { c 0 = σ 2 , c 1 = σ 2 f ( D ) / 2 , c 2 = σ 2 f ( 2 D ) / 2 , }
Z out = ( 1 / 2 1 / 2 0 1 / 2 1 / 2 1 / 2 1 / 2 0 1 / 2 1 / 2 0 1 / 2 1 / 2 1 / 2 1 / 2 0 ) .
λ out = ( c 0 + 2 c 1 + c 2 c 0 2 c 1 + c 2 c 0 c 2 c 0 c 2 ) = ( 4 σ 2 f ( D ) f ( 2 D ) / 2 f ( D ) f ( 2 D ) / 2 f ( 2 D ) / 2 f ( 2 D ) / 2 ) .
σ 2 > f ( D ) / 4 + f ( 2 D ) / 8.
σ 2 = 1 2 f ( 2 D ) .
K out = 1 2 ( a b c 0 a b 0 c a b c 0 a b 0 c ) ,
a = 4 σ 2 f ( D ) f ( 2 D ) / 2 ,
b = f ( D ) f ( 2 D ) / 2 ,
c = f ( 2 D ) ,
K out 1 = 1 2 ( 1 / a 1 / a 1 / a 1 / a 1 / b 1 / b 1 / b 1 / b 2 / c 0 2 / c 0 0 2 / c 0 2 / c ) .
w 0 = α 0 u 0 + j = 1 N int α j w j ,
f i , 0 = def ( w 0 w i ) 2 = α 0 2 + j = 1 N int α j f i , j 1 j < k N int α j α k f j , k + ( 1 k = 1 N int α k ) ( σ i 2 j = 1 N int α j σ j 2 ) .
f i , 0 = α 0 2 + j = 1 N int α j f i , j 1 j < k N int α j α k f j , k     s .t .   j = 1 N int α j = 1.
f i , 0 = α 0 2 + j = 1 N int α j f i , j 1 j < k N int α j α k f j , k + σ 2 ( 1 j = 1 N int α j ) 2     for   i = 1 , , N int ,
σ 2 = α 0 2 + σ 2 ( j = 1 N int α j ) 2 1 j < k N int α j α k f j , k .
j = 1 N int ( 2 σ 2 f i , j ) α j = 2 σ 2 f i , 0     for   i = 1 , , N int ,
α 0 2 = [ 1 ( j = 1 N int α j ) 2 ] σ 2 + 1 j < k N int α j α k f j , k ,
j = 1 N int C i , j α j = C 0 , i     for   i = 1 , , N int ,
α 0 2 = σ 2 j = 1 N int C 0 , j α j .
K 1 = K p 1 K 2 1 K 1 1 .
u 0 = 1 α 0 ( w 0 j = 1 N int α j w j ) ,
M 1 A x = M 1 b ,
( K T S T C n 1 S K + I ) u = ( K T S T C n 1 d ) .
M = arg   min M A x M x 2 0 = ( A M ) x 2 M = 2 ( M A ) x x T M C x = A C x ,
M = diag ( m ) = diag ( A C x ) diag ( C x ) 1 .
M = diag ( A ) ,
Q = arg   min Q Q A x x 2 0 = Q A x x 2 Q = 2 ( Q A I ) C x A T Q A C x A T = C x A T .
Q = diag ( q ) = diag ( C x A T ) diag ( A C x A T ) 1 .
Q i , i = A i , i j A i , j 2 ,     Q i , j i = 0.
( S T C n 1 S + K T K 1 ) w = S T C n 1 d ,
( K T S T C n 1 S K + I ) u = K T S T C n 1 d
N CG ops ( N overhead + 33 N CG iter ) N ,
N PCG ops ( N overhead + 34 N PCG iter ) N ,
c 0 = c ( 0 ) = σ 2 ,
c 1 = c ( r / 2 ) = σ 2 f ( r / 2 ) / 2 ,
c 2 = c ( r / 2 ) = σ 2 f ( r / 2 ) / 2 ,
c 3 = c ( r ) = σ 2 f ( r ) / 2 ,
c 4 = c ( 2 r ) = σ 2 f ( 2 r ) / 2 ,
( c 0 c 3 c 4 c 3 c 3 c 0 c 3 c 4 c 4 c 3 c 0 c 3 c 3 c 4 c 3 c 0 ) ( α 1 α 2 α 3 α 4 ) = ( c 2 c 2 c 2 c 2 ) .
α 1 = α 2 = α 3 = α 4 = c 2 c 0 + 2 c 3 + c 4 ,
α 0 = ± c 0 4 c 2 2 c 0 + 2 c 3 + c 4 .
( c 0 c 3 c 2 c 3 c 0 c 2 c 2 c 2 c 0 ) ( α 1 α 2 α 3 ) = ( c 1 c 1 c 1 ) .
α 1 = α 2 = c 1 ( c 0 c 2 ) c 0 ( c 0 + c 3 ) 2 c 2 2 ,
α 3 = c 1 ( c 0 2 c 2 + c 3 ) c 0 ( c 0 + c 3 ) 2 c 2 2 ,
α 0 = ± c 0 c 1 2 ( 3 c 0 4 c 2 + c 3 ) c 0 ( c 0 + c 3 ) 2 c 2 2 .
α 1 = α 2 = α 3 = α 4 = c 1 c 0 + 2 c 2 + c 3 ,
α 0 = ± c 0 4 c 1 2 c 0 + 2 c 2 + c 3 .
A = S T C n 1 S + K T K 1 ,
b = S T C n 1 d .
r 0 = b A w 0 = S T C n 1 ( d S w 0 ) K T K 1 w 0 .
A = K T S T C n 1 S K + I ,
b = K T S T C n 1 d ,
r 0 = b A u 0 = K T S T C n 1 ( d S K u 0 ) u 0 .
N ops ( K ) = N ops ( K T ) = N ops ( K 1 ) = N ops ( K T ) = 6 N u 14 6 N ,
N ops ( C n 1 ) = M 2 N .
N ops ( S ) = N ops ( S T ) 4 N .
N ops ( A ) 2 N ops ( K ) + 2 N ops ( S ) + N ops ( C n 1 ) + N 23 N .
N ops ( r 0 ) 2 N ops ( K ) + 2 N ops ( S ) + N ops ( C n 1 ) + M + N 25 N

Metrics