Opened 3 years ago
Closed 3 years ago
#22951 closed enhancement (fixed)
Integrated curves and geodesics on manifolds
Reported by:  karimvanaelst  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  geometry  Keywords:  curve, geodesic, manifold 
Cc:  egourgoulhon, mbejger, mmancini, tscrim  Merged in:  
Authors:  Karim Van Aelst  Reviewers:  Eric Gourgoulhon, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  1c7e727 (Commits)  Commit:  1c7e7279ab269d9ac9e05696eac77a2fe5cdbf3e 
Dependencies:  Stopgaps: 
Description
This ticket implements curves defined by a system of differential equations, in particular geodesics on differentiable manifolds.
This is part of the SageManifolds project ; see the metaticket #18528 for an overview.
Change History (30)
comment:1 Changed 3 years ago by
 Commit changed from c58d90285342fe430a186343b3ca2d86b905802c to 2328a7f7a61314952a72fd35a269770b5e2bb114
comment:2 Changed 3 years ago by
 Cc egourgoulhon mbejger mmancini tscrim added
comment:3 Changed 3 years ago by
 Commit changed from 2328a7f7a61314952a72fd35a269770b5e2bb114 to 6928d9df219e28a5a94af9a8ab5d133bb49ae001
Branch pushed to git repo; I updated commit sha1. New commits:
6928d9d  more numerical solvers, an analytical solver, parents, parameters detected

comment:4 Changed 3 years ago by
 Status changed from new to needs_review
comment:5 Changed 3 years ago by
 Reviewers set to Eric Gourgoulhon
 Status changed from needs_review to needs_work
Thank you very much for this piece of work! It's a great enhancement to manifolds in Sage. Moreover the code looks very good and the documentation is carefully written and nice. A first quick comments (more will follow):
 Some doctests fail due to some extra (debug?) messages:
File "src/sage/manifolds/differentiable/manifold_homset.py", line 575, in sage.manifolds.differentiable.manifold_homset.IntegratedCurveSet Failed example: c = H(eqns_rhs, vels, t, v, name='c') ; c Expected: Integrated curve c in the 2dimensional differentiable manifold M Got: The curve was correctly set. No parameter appears in the differential system defining the curve. Integrated curve c in the 2dimensional differentiable manifold M
 Another doctest failure is that of
c.__reduce__()
in line 556 ofintegrated_curve.py
, apparently due to<class 'sage.manifolds.differentiable.manifold_homset.IntegratedCurveSet_with_category.element_class'>
appearing instead of<class 'sage.manifolds.differentiable.integrated_curve.IntegratedCurveSet_with_category.element_class'>
 Some methods are too verbose, e.g.
solve
,tangent_vector_eval_at
,plot_integrated
and__call__
in classIntegratedCurve
;verbose=False
should be the default (this seems a general policy in Sage)
 The documentation fails to build:
 in
integrated_curve.py
, line 1712: the continuation mark....:
is invalid in a plot directive; line 2413: a final quote is missing in'epolar_ON)
 in
manifold_homset.py
, lines 938 and 1386:EXAMPLES:
must be replaced byEXAMPLES::
 in
comment:6 Changed 3 years ago by
A few more comments:
 Do not use
.keys()
to iterate over the keys of a dictionary, but simply the dictionary itself, i.e. replacefor key in parameters_values.keys():
byfor key in parameters_values:
. Similarly, do not use.keys()
to check for a key in a dictionary, i.e. replaceif 'cubic spline' in self._interpolations.keys():
byif 'cubic spline' in self._interpolations:
 The rendering of some math formulas in the html documentation is not correct: the antislashes must be suppressed in
(v\_th0, v\_ph0)
andepolar\_ON
, etc. Morevover, some:MATH:
appear explicitely in the html output (example in the documentation of classIntegratedAutoparallelCurve
).  In the documentation of
solve_analytical
, do not writeboolean 'FALSE'
but
boolean ``False``
comment:7 Changed 3 years ago by
 Commit changed from 6928d9df219e28a5a94af9a8ab5d133bb49ae001 to 1adbcdc288727d60413f08b0dac7a78cae86dd48
Branch pushed to git repo; I updated commit sha1. New commits:
1adbcdc  corrections to doctests, documentation, iteration over dictionary, and verbose set to False everywhere

comment:8 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:9 followup: ↓ 11 Changed 3 years ago by
Thanks for the changes. Here are more comments:
 There are still some failed doctests:
5 items had failures: 1 of 12 in sage.manifolds.differentiable.integrated_curve.IntegratedAutoparallelCurve.__reduce__ 1 of 27 in sage.manifolds.differentiable.integrated_curve.IntegratedCurve 1 of 98 in sage.manifolds.differentiable.integrated_curve.IntegratedCurve.? 1 of 13 in sage.manifolds.differentiable.integrated_curve.IntegratedCurve.__reduce__ 1 of 14 in sage.manifolds.differentiable.integrated_curve.IntegratedGeodesic.__reduce__ [369 tests, 5 failures, 43.70 s]  sage t long warnlong 82.5 src/sage/manifolds/differentiable/integrated_curve.py # 5 doctests failed
 The method
__call__
of classIntegratedCurve
should return a manifold point, not a list of coordinates  Lines 428437 of
integrated_curve.py
could be replaced by a mereif initial_pt not in chart.domain(): raise ValueError("initial point should be in the " + "domain of the chart")
Btw notice that, by convention, error messages start with a lower case letter and do not end by any ponctuation mark.  To ensure that the
print
function used inintegrated_curve.py
complies with Python3, please insertfrom __future__ import print_function
in the heading of this file.  I am wondering whether it is worth to keep the arguments
is_identity
andis_isomorphism
in the__init__
's of the integrated curve classes and in the related construction methods of classDifferentiableManifold
; this adds some code complexity for something which regards only curves (a,b) > R and for which it is difficult to imagine a use case... Do you agree?  Maybe the documentation TOC would be more descriptive if the title "Integrated Curves in Manifolds" in line 2 of
integrated_curve.py
were replaced by "Integrated Curves and Geodesics in Manifolds".  In the docstring of method
plot_integrated
, the keyword argumentsdisplay_tangent
,plot_points_tangent
,color_tangent
andwidth_tangent
are not documented.  In the second sentence of the main docstring in
manifold_homset.py
, starting line 9, the classesIntegratedCurveSet
,IntegratedAutoparallelCurveSet
andIntegratedGeodesicSet
should be added to the list of subclasses ofDifferentiableManifoldHomset
comment:10 Changed 3 years ago by
 Commit changed from 1adbcdc288727d60413f08b0dac7a78cae86dd48 to 80eb4690bd57eb744218ea7f8805d34c8f036156
Branch pushed to git repo; I updated commit sha1. New commits:
9d1bab6  Merge branch 'public/manifolds/integrated_curve' of git://trac.sagemath.org/sage into develop

80eb469  doctests failures reported in last review corrected, method __call__ now returns a manifold point, syntax of error messages corrected, print_function imported, implementation relative to arguments is_identity and is_isomorphism removed (in particular, identity map not implemented by method one of parent classes), documentation completed as suggested in last review, slight corrections in method 'solve'

comment:11 in reply to: ↑ 9 ; followup: ↓ 12 Changed 3 years ago by
 Doctests failures reported in last review were due to implementation adapted to version 8.0.beta5 instead of version 8.0.rc0; doctests are now consistent with version 8.0.rc0.
 Method
__call__
of classIntegratedCurve
now does return a manifold point instead of a list of coordinates, which is indeed much more consistent with the purpose of the class (which is to represent curves in manifold).  Former lines 428437 (which now are lines 440449) cannot be replaced by the suggested lines, since the fact that some initial coordinates may be expressions needs to be taken into account.
print_function
is now imported. All implementation relative to arguments
is_identity
andis_isomorphism
is removed. In particular, no identity map is implemented by methodone
of the parent classes; this is justified by the lack of relevance of the identity map within the framework of the classes of this ticket, whose purpose is mainly devoted to numerical issues (therefore, any user is left free to set a numerical version of the identity if needed).  The title of the documentation of
integrated_curve.py
, now in line 3, is now "Integrated Curves and Geodesics in Manifolds".  The documentation of method
plot_integrated
is now complete.  The main docstring of
manifold_homset.py
is now complete.
Replying to egourgoulhon:
Thanks for the changes. Here are more comments:
 There are still some failed doctests:
5 items had failures: 1 of 12 in sage.manifolds.differentiable.integrated_curve.IntegratedAutoparallelCurve.__reduce__ 1 of 27 in sage.manifolds.differentiable.integrated_curve.IntegratedCurve 1 of 98 in sage.manifolds.differentiable.integrated_curve.IntegratedCurve.? 1 of 13 in sage.manifolds.differentiable.integrated_curve.IntegratedCurve.__reduce__ 1 of 14 in sage.manifolds.differentiable.integrated_curve.IntegratedGeodesic.__reduce__ [369 tests, 5 failures, 43.70 s]  sage t long warnlong 82.5 src/sage/manifolds/differentiable/integrated_curve.py # 5 doctests failed
 The method
__call__
of classIntegratedCurve
should return a manifold point, not a list of coordinates Lines 428437 of
integrated_curve.py
could be replaced by a mereif initial_pt not in chart.domain(): raise ValueError("initial point should be in the " + "domain of the chart")Btw notice that, by convention, error messages start with a lower case letter and do not end by any ponctuation mark. To ensure that the
integrated_curve.py
complies with Python3, please insertfrom __future__ import print_functionin the heading of this file. I am wondering whether it is worth to keep the arguments
is_identity
andis_isomorphism
in the__init__
's of the integrated curve classes and in the related construction methods of classDifferentiableManifold
; this adds some code complexity for something which regards only curves (a,b) > R and for which it is difficult to imagine a use case... Do you agree? Maybe the documentation TOC would be more descriptive if the title "Integrated Curves in Manifolds" in line 2 of
integrated_curve.py
were replaced by "Integrated Curves and Geodesics in Manifolds". In the docstring of method
plot_integrated
, the keyword argumentsdisplay_tangent
,plot_points_tangent
,color_tangent
andwidth_tangent
are not documented. In the second sentence of the main docstring in
manifold_homset.py
, starting line 9, the classesIntegratedCurveSet
,IntegratedAutoparallelCurveSet
andIntegratedGeodesicSet
should be added to the list of subclasses ofDifferentiableManifoldHomset
comment:12 in reply to: ↑ 11 ; followup: ↓ 14 Changed 3 years ago by
 Status changed from needs_review to needs_work
Replying to karimvanaelst:
Thanks for the changes.
 Doctests failures reported in last review were due to implementation adapted to version 8.0.beta5 instead of version 8.0.rc0; doctests are now consistent with version 8.0.rc0.
OK.
 Method
__call__
of classIntegratedCurve
now does return a manifold point instead of a list of coordinates, which is indeed much more consistent with the purpose of the class (which is to represent curves in manifold).
OK, very good.
 Former lines 428437 (which now are lines 440449) cannot be replaced by the suggested lines, since the fact that some initial coordinates may be expressions needs to be taken into account.
OK.
print_function
is now imported. All implementation relative to arguments
is_identity
andis_isomorphism
is removed.
is_identity
and is_isomorphism
still appear in the documentation of the integrated curve methods of class DifferentiableManifold
...
In particular, no identity map is implemented by method
one
of the parent classes; this is justified by the lack of relevance of the identity map within the framework of the classes of this ticket, whose purpose is mainly devoted to numerical issues (therefore, any user is left free to set a numerical version of the identity if needed).
Indeed.
 The title of the documentation of
integrated_curve.py
, now in line 3, is now "Integrated Curves and Geodesics in Manifolds".
Thanks.
 The documentation of method
plot_integrated
is now complete.
In that documentation, the default value of plot_points_tangent
should appear as 10, not 75.
 The main docstring of
manifold_homset.py
is now complete.
Thanks.
A few minor points regarding the Poincaré halfplane example in the main docstring of integrated_curve.py
:
 typo:
Poicaré
>Poincaré
 the plot does not appear in the documentation (missing
sphinx_plot
)  on this example, we have
sage: c(0) == p True
butsage: c.tangent_vector_eval_at(0) == v False
Indeed,c.tangent_vector_eval_at(0)
is a tangent vector atp
:sage: c.tangent_vector_eval_at(0) in M.tangent_space(p) True
but it does not coincide withv
:sage: c.tangent_vector_eval_at(0).display() 1.0865965337902876 d/dx + 1.536951899804222 d/dy
Finally, as revealed by the patchbot, the syntax for the example blocs should be EXAMPLES:
, not EXAMPLE:
, even if there is only one example.
comment:13 Changed 3 years ago by
 Commit changed from 80eb4690bd57eb744218ea7f8805d34c8f036156 to a91fb48e8168731d1377b70b24f90a7319d66bf6
Branch pushed to git repo; I updated commit sha1. New commits:
a91fb48  changes suggested by review, simpler 'an_element' methods

comment:14 in reply to: ↑ 12 ; followup: ↓ 15 Changed 3 years ago by
 Status changed from needs_work to needs_review
Replying to egourgoulhon:
is_identity
andis_isomorphism
no longer appear in the documentation of the integrated curve methods of classDifferentiableManifold
as it should be.
 The default value of
plot_points_tangent
indicated in the documentation ofplot_integrated
is now correctly set to 10.
 Method
tangent_vector_eval_at
evaluates a vector tangent to the curve using an interpolation. If this method is called on the initial point of the curve, the method does not try to return the initial tangent vector provided by the user when the curve was set, although this would obviously always be the most correct result. One reason for this is that the initial tangent vector may be defined in terms of expressions, i.e. it may have non numerical components. On the contrary,tangent_vector_eval_at
always returns a fully numerical tangent vector, since it uses an interpolation, which itself was built from a numerical solution, which itself could only be computed if numerical values were provided for all the parameters of the system defining the curve (in particular, if some components of the initial tangent vector were expressions, the user should have provided numerical values for those when calling methodsolve
). This explains the obvious lack of precision of this method in the case of the Poincaré halfplane example pointed out in comment:12. Of course, to face this and get better results, one may merely reduce the step of integration when calling methodsolve
.
 All
EXAMPLE:
were changed toEXAMPLES:
as they should.
comment:15 in reply to: ↑ 14 Changed 3 years ago by
 Status changed from needs_review to positive_review
Thanks for these last changes. I agree with your comments on tangent_vector_eval_at
.
The ticket is in very good shape; the patchbot reports some "Timed out" failures, but they are not related to this ticket (this is well known issue, discussed here). Thank you very much for this nice work!
comment:16 followup: ↓ 17 Changed 3 years ago by
 Commit changed from a91fb48e8168731d1377b70b24f90a7319d66bf6 to 7479f47d6514428ad0bd00269af33b2fb495354c
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
7479f47  'init' of autoparallel_curve now robust to change of default chart, tiny corrections in documentation

comment:17 in reply to: ↑ 16 Changed 3 years ago by
Commit 7479f47 mainly corrects __init__
of IntegratedAutoparallelCurve
in order to obtain the right equations from the affine connection in terms of the chart chosen by the user, even if it is not the default chart.
comment:18 Changed 3 years ago by
 Status changed from needs_review to positive_review
Thanks for these last improvements. Everything looks good to me.
comment:19 Changed 3 years ago by
 Status changed from positive_review to needs_work
sage t long warnlong 85.3 src/sage/manifolds/differentiable/integrated_curve.py ********************************************************************** File "src/sage/manifolds/differentiable/integrated_curve.py", line 171, in sage.manifolds.differentiable.integrated_curve.IntegratedCurve Failed example: c = M.integrated_curve(eqns, D, (t, 0, 5), v, name='c', verbose=True) Expected: The curve was correctly set. Parameters appearing in the differential system defining the curve are [B_0, L, T, q, m]. Got: The curve was correctly set. Parameters appearing in the differential system defining the curve are [B_0, L, T, m, q]. ********************************************************************** File "src/sage/manifolds/differentiable/integrated_curve.py", line 925, in sage.manifolds.differentiable.integrated_curve.IntegratedCurve.? Failed example: sol = c.solve(parameters_values={m:1, q:1, L:10, T:1}) Expected: Traceback (most recent call last): ... ValueError: numerical values should be provided for each of the parameters [B_0, L, T, q, m] Got: <BLANKLINE> Traceback (most recent call last): File "/mnt/disk/home/release/Sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 509, in _run self.compile_and_execute(example, compiler, test.globs) File "/mnt/disk/home/release/Sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 872, in compile_and_execute exec(compiled, globs) File "<doctest sage.manifolds.differentiable.integrated_curve.IntegratedCurve.?[10]>", line 1, in <module> sol = c.solve(parameters_values={m:Integer(1), q:Integer(1), L:Integer(10), T:Integer(1)}) File "/mnt/disk/home/release/Sage/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/integrated_curve.py", line 1015, in solve "{}".format(sorted(self._parameters))) ValueError: numerical values should be provided for each of the parameters [B_0, L, T, m, q] ********************************************************************** 2 items had failures: 1 of 29 in sage.manifolds.differentiable.integrated_curve.IntegratedCurve 1 of 98 in sage.manifolds.differentiable.integrated_curve.IntegratedCurve.? [387 tests, 2 failures, 49.99 s]
comment:20 Changed 3 years ago by
 Commit changed from 7479f47d6514428ad0bd00269af33b2fb495354c to 0f0c67b2de1300f0f39a2e6592be1cea64862729
Branch pushed to git repo; I updated commit sha1. New commits:
0f0c67b  Various types of cleanup.

comment:21 followup: ↓ 23 Changed 3 years ago by
 Milestone changed from sage8.0 to sage8.1
 Reviewers changed from Eric Gourgoulhon to Eric Gourgoulhon, Travis Scrimshaw
 Status changed from needs_work to needs_review
This should fix the doctest errors. I also did some other cleanup in terms of code, PEP8, and documentation. In particular, I suspect the pdf doc would not have built previously.
comment:22 Changed 3 years ago by
 Commit changed from 0f0c67b2de1300f0f39a2e6592be1cea64862729 to 95ef0140f61111d1d908f05b6289918d5077c914
Branch pushed to git repo; I updated commit sha1. New commits:
95ef014  Fix some doctests and sphinx_plot trivial errors in integrated curves

comment:23 in reply to: ↑ 21 ; followup: ↓ 24 Changed 3 years ago by
Replying to tscrim:
This should fix the doctest errors. I also did some other cleanup in terms of code, PEP8, and documentation. In particular, I suspect the pdf doc would not have built previously.
Thanks a lot for the cleanup! The above commit fixes an error in a PLOT directive (missing =
sign), and fixes some failed doctests in manifold.py
and manifold_homset.py
due to the replacement of "w.r.t." by "with respect to". It also adds some extra cleanup.
I let you set the ticket back to positive review if this is OK for you.
comment:24 in reply to: ↑ 23 Changed 3 years ago by
 Status changed from needs_review to positive_review
Replying to egourgoulhon:
Replying to tscrim:
This should fix the doctest errors. I also did some other cleanup in terms of code, PEP8, and documentation. In particular, I suspect the pdf doc would not have built previously.
Thanks a lot for the cleanup! The above commit fixes an error in a PLOT directive (missing
=
sign),
Thanks.
and fixes some failed doctests in
manifold.py
andmanifold_homset.py
due to the replacement of "w.r.t." by "with respect to". It also adds some extra cleanup.
Sorry; I blindly did a search and replace in integrated_curves.py
(although I do prefer the explicitness).
I let you set the ticket back to positive review if this is OK for you.
Yep, it is all good. Thank you.
comment:25 Changed 3 years ago by
 Status changed from positive_review to needs_work
sage t long src/sage/manifolds/differentiable/integrated_curve.py ********************************************************************** File "src/sage/manifolds/differentiable/integrated_curve.py", line 239, in sage.manifolds.differentiable.integrated_curve.IntegratedCurve Failed example: v.display() Expected: 0.9303968397216424 d/dx1  0.3408080563014475 d/dx2 + 1.0000000000000004 d/dx3 Got: 0.9303968397216426 d/dx1  0.3408080563014474 d/dx2 + 1.0000000000000004 d/dx3 ********************************************************************** File "src/sage/manifolds/differentiable/integrated_curve.py", line 1669, in sage.manifolds.differentiable.integrated_curve.IntegratedCurve.? Failed example: tg_vec[:] Expected: [0.7392639473853356, 0.6734182305341726, 1.0000000000000007] Got: [0.7392639473853356, 0.6734182305341726, 1.0000000000000009] ********************************************************************** 2 items had failures: 1 of 28 in sage.manifolds.differentiable.integrated_curve.IntegratedCurve 1 of 98 in sage.manifolds.differentiable.integrated_curve.IntegratedCurve.? [380 tests, 2 failures, 68.55 s]
sage t long src/sage/manifolds/differentiable/manifold.py ********************************************************************** File "src/sage/manifolds/differentiable/manifold.py", line 2663, in sage.manifolds.differentiable.manifold.DifferentiableManifold.? Failed example: tgt_vec[:] Expected: [0.8481008455360024, 0.5298346120470748, 1.0000000000000007] Got: [0.8481008455360024, 0.5298346120470748, 1.0000000000000004] ********************************************************************** 1 item had failures: 1 of 161 in sage.manifolds.differentiable.manifold.DifferentiableManifold.? [490 tests, 1 failure, 35.89 s]
sage t long src/sage/manifolds/differentiable/manifold.py ********************************************************************** File "src/sage/manifolds/differentiable/manifold.py", line 2797, in sage.manifolds.differentiable.manifold.DifferentiableManifold.? Failed example: tgt_vec[:] Expected: [0.9999999999999732, 1.016513736236512] Got: [0.9999999999999732, 1.0165137362366825] ********************************************************************** File "src/sage/manifolds/differentiable/manifold.py", line 2917, in sage.manifolds.differentiable.manifold.DifferentiableManifold.? Failed example: tgt_vec[:] Expected: [1.090742147346732, 0.620568327518154] Got: [1.0907421473467311, 0.6205683275181549] ********************************************************************** 1 item had failures: 2 of 161 in sage.manifolds.differentiable.manifold.DifferentiableManifold.? [490 tests, 2 failures, 65.30 s]
You should probably add an # abs tol to all numerical results unless you intentionally write code with IEEE floating point reproducibility in mind.
comment:26 followup: ↓ 27 Changed 3 years ago by
 Commit changed from 95ef0140f61111d1d908f05b6289918d5077c914 to 1c7e7279ab269d9ac9e05696eac77a2fe5cdbf3e
Branch pushed to git repo; I updated commit sha1. New commits:
1c7e727  absolute tolerance in doctests, corrections regarding tests on interpolations

comment:27 in reply to: ↑ 26 Changed 3 years ago by
Thanks a lot for all the corrections.
As suggested, an absolute tolerance (# abs tol) was added to all numerical results in the doctests.
Additionally, methods __call__
and tangent_vector_eval_at
of class integrated_curve
were modified following the model of corrections made in method plot_integrated
(starting on lines 1907, now 1908, and 2084, now 2085) in commit 0f0c67b.
(Precisions about these are given here in case of future improvements regarding interpolation.
The corrections in methods __call__
, tangent_vector_eval_at
and plot_integrated
concern tests on the class of the objects implementing interpolations of the numerical solutions computed with method solve
.
For now, only class sage.calculus.interpolation.Spline
is used, but these tests anticipate the fact that new classes implementing other methods of interpolation might be introduced.
Of course, in such case, tests such as if not isinstance(interpolation[0], Spline):
(such as in lines 1604, 1694,..) should become if not isinstance(interpolation[0], (Spline, OtherInterpolationClass)):
.
But modifications of the source code induced by the introduction of new interpolation classes should be limited to the above tests and the content of method interpolate
.
This means that an instance of OtherInterpolationClass
should allow to be called as it is done in lines 1609, 1709, 1954, ..., and should admit a method derivative
to be called in lines 1703, 2018...)
comment:28 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:29 Changed 3 years ago by
 Status changed from needs_review to positive_review
Thanks for the update. LGTM and the patchbot gives green light.
comment:30 Changed 3 years ago by
 Branch changed from public/manifolds/integrated_curve to 1c7e7279ab269d9ac9e05696eac77a2fe5cdbf3e
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
bugsremoved, documentation completed, mapping implemented