Ever since I discovered the faer linear algebra library I wanted to rewrite gomez into it. For two reasons:
Performance. The benchmarks for faer are very impressive. Moreover, the low level API allows to do operations, for which I am now forced to use cloning, in place.
API. nalgebra is very flexible with the matrix storage, but it also means that it's very trait-heavy (our public API is unnecessarily complex due to that, and the implementations of solvers are even worse). Interface when using faer will be much simpler.
Half a year ago I actually spent some time on implementing the algorithms using faer, and after initial struggles I managed to do most of them (and some more, and in a much more modular structure). The code that I have is for an old version of faer and a lot of changes were made since that, but they should be mostly cosmetic.
The plan is as follows:
Make some improvements to the API (more on that below).
Release 0.5.0.
Migrate everything to faer.
Release 0.6.0.
For a limited time period, make patches to 0.5.x branch if needed. This would be for people who want to continue using nalgebra.
Before fully migrating to faer, I would like to do some unrelated (or partly related) improvements to the API. Now I can think of these:
[x] Make function optimization a first-class citizen. Rename the next methods in Solver and Optimizer traits to solve_next and opt_next, respectively, so that they don't clash (see dd6524a).
[x] Remove apply_eval from the Function trait. A problem is either a system or function, not both. I guess this was a work around for being able to "solve" some systems by algorithms that only implemented the Optimizer trait. Instead of apply_eval, all Optimizers should also implement the Solver trait (not automatically, but as a guideline).
[x] Remove Dim associated type from the Problem trait. faer supports only dynamically sized matrices. Removing the type now should be an incremental change towards to final migration. Move the dim method from the Problem trait to the Domain type and make its return type usize.
[x] ~Add jacobian method to the System trait and gradient and hessian methods to the Function trait and provide default implementations using finite difference approximations.~ EDIT: With the current implementation of finite differences in gomez, this would allocate memory on every call. So I will postpone this to after faer rewrite, where the core API will be more functional and low-level.
[x] Remove ProblemError and don't return Result in System::eval and Function::apply. Encountering invalid dimensionality is a bug in the solver/optimizer not respecting the value in Domain::dim and so panic! is appropriate. Invalid values (infinity, NaN) should be detected by the solver. This will simplify APIs a bit and might also result in faster & smaller code (less branches). Transitively, other error types and corresponding Result returning methods will also be removed (JacobianError, etc.).
[x] Rename Problem::Scalar associated type to Problem::Field (seems like a better name considering its usage in Rust ecosystem). Introduce custom RealField trait having nalgebra's (later faer's) RealField as a super trait, and make Problem::Field type be constrained by our RealField trait. Move EPSILON_CBRT and EPSILON_SQRT constants to this trait (and use proper values for f32).
[x] Remove Variable and VariableBuilder and add specific constructors to Domain for unconstrained and rectangular domain. This will make Domain more flexible (we might add support for other domain types, for example spherical domain). But user should still be able to somehow specify custom scale/magnitude for variables.
[x] ~Make Problem::domain return &Domain instead of Domain. This will shift the responsibility of keeping the domain instance from the call-site (before creating the solver and throughout the solving process) to the problem type itself. Thanks to that, many functions will not need separate parameter for the domain.~ EDIT: This would be less convenient on the user side. Instead, keep the current low-level API and focus on high-level API which will hide these details.
[x] Remove cuckoo search algorithm. I don't think it provides much value, it was a relic from my experimentation in the past. I believe that LIPO or a more widely-used meta-heuristics algorithm (e.g., differential evolution) should be our focus.
[x] Remove the population module. As cuckoo search will be removed and it is currently the only population-based algorithm in gomez, there is no point in having this module in gomez (now). We may reintroduce it later, potentially in a different shape.
[x] Remove FunctionResultExt and VectorDomainExt. These are poor API.
[x] Hide the testing module behind a feature flag.
[x] Add TestFunction counterpart to the TestSystem in the testing module.
[x] Rename SolveError in testing module to something more generic (e.g., TestError) so the naming makes more sense in the context of optimization.
[x] ~Make Solver and Optimizer the only things exported from the prelude. Since Problem and System/Function are traits to be implemented by the user, it is probably better to explicitly import them.~ EDIT: Such a small prelude is probably not worthy of having a prelude. Instead, everything should be imported explicitly. Once there is high-level API, it will be encouraged and the Solver/Optimizer traits should not be necessary to import to use the high-level API.
[x] ~Introduce SolveIter<'a> and OptimizeIter<'a> which implement Iterator<Item = Result<('a x, 'a fx), S::Error>> (no lifetime 'a for fx in optimization case). Add solve(solver, problem, x, fx) and optimize(optimizer, problem, x) methods to the Solver and Optimizer traits, respectively, with default implementation that will simply construct the corresponding iterator and return it. This will be the high-level API, which still allows quite flexible control over the process (e.g., iter.take(max_iters).find(|result| result.map(|(x, fx)| fx.norm() <= 1e-6).unwrap_or(true))).~ Nevermind, I forgot that for Iterator::Item be a reference, I would need a lending iterator. So instead I implemented the drivers that to some extent mimic the iterator API.
[x] Move everything (what remains) from the core module to the root of the library.
[x] Remove RepulsiveSystem type. It is still a good idea, but it is currently a noop and I am not planning to spend time on it now. We may reintroduce it in the future.
[x] Migrate from rand to fastrand. It is designed to be fast (whereas in rand choosing fast generator requires conscious "effort") and has a bit simpler API. Nevertheless, still require the generator as an explicit parameter to support determinism (user sending generator initialized with a fixed seed).
After all these changes are done and 0.5.0 is released, then I will migrate the whole library from nalgebra to faer.
Ever since I discovered the faer linear algebra library I wanted to rewrite gomez into it. For two reasons:
Half a year ago I actually spent some time on implementing the algorithms using faer, and after initial struggles I managed to do most of them (and some more, and in a much more modular structure). The code that I have is for an old version of faer and a lot of changes were made since that, but they should be mostly cosmetic.
The plan is as follows:
Before fully migrating to faer, I would like to do some unrelated (or partly related) improvements to the API. Now I can think of these:
nextmethods inSolverandOptimizertraits tosolve_nextandopt_next, respectively, so that they don't clash (see dd6524a).apply_evalfrom theFunctiontrait. A problem is either a system or function, not both. I guess this was a work around for being able to "solve" some systems by algorithms that only implemented theOptimizertrait. Instead ofapply_eval, allOptimizers should also implement theSolvertrait (not automatically, but as a guideline).Dimassociated type from theProblemtrait. faer supports only dynamically sized matrices. Removing the type now should be an incremental change towards to final migration. Move thedimmethod from theProblemtrait to theDomaintype and make its return typeusize.jacobianmethod to theSystemtrait andgradientandhessianmethods to theFunctiontrait and provide default implementations using finite difference approximations.~ EDIT: With the current implementation of finite differences in gomez, this would allocate memory on every call. So I will postpone this to after faer rewrite, where the core API will be more functional and low-level.ProblemErrorand don't returnResultinSystem::evalandFunction::apply. Encountering invalid dimensionality is a bug in the solver/optimizer not respecting the value inDomain::dimand sopanic!is appropriate. Invalid values (infinity, NaN) should be detected by the solver. This will simplify APIs a bit and might also result in faster & smaller code (less branches). Transitively, other error types and correspondingResultreturning methods will also be removed (JacobianError, etc.).Problem::Scalarassociated type toProblem::Field(seems like a better name considering its usage in Rust ecosystem). Introduce customRealFieldtrait having nalgebra's (later faer's)RealFieldas a super trait, and makeProblem::Fieldtype be constrained by ourRealFieldtrait. MoveEPSILON_CBRTandEPSILON_SQRTconstants to this trait (and use proper values forf32).VariableandVariableBuilderand add specific constructors toDomainfor unconstrained and rectangular domain. This will makeDomainmore flexible (we might add support for other domain types, for example spherical domain). But user should still be able to somehow specify custom scale/magnitude for variables.Problem::domainreturn&Domaininstead ofDomain. This will shift the responsibility of keeping the domain instance from the call-site (before creating the solver and throughout the solving process) to the problem type itself. Thanks to that, many functions will not need separate parameter for the domain.~ EDIT: This would be less convenient on the user side. Instead, keep the current low-level API and focus on high-level API which will hide these details.populationmodule. As cuckoo search will be removed and it is currently the only population-based algorithm in gomez, there is no point in having this module in gomez (now). We may reintroduce it later, potentially in a different shape.FunctionResultExtandVectorDomainExt. These are poor API.testingmodule behind a feature flag.TestFunctioncounterpart to theTestSystemin thetestingmodule.SolveErrorintestingmodule to something more generic (e.g.,TestError) so the naming makes more sense in the context of optimization.SolverandOptimizerthe only things exported from theprelude. SinceProblemandSystem/Functionare traits to be implemented by the user, it is probably better to explicitly import them.~ EDIT: Such a small prelude is probably not worthy of having a prelude. Instead, everything should be imported explicitly. Once there is high-level API, it will be encouraged and theSolver/Optimizertraits should not be necessary to import to use the high-level API.SolveIter<'a>andOptimizeIter<'a>which implementIterator<Item = Result<('a x, 'a fx), S::Error>>(no lifetime'afor fx in optimization case). Addsolve(solver, problem, x, fx)andoptimize(optimizer, problem, x)methods to theSolverandOptimizertraits, respectively, with default implementation that will simply construct the corresponding iterator and return it. This will be the high-level API, which still allows quite flexible control over the process (e.g.,iter.take(max_iters).find(|result| result.map(|(x, fx)| fx.norm() <= 1e-6).unwrap_or(true))).~ Nevermind, I forgot that forIterator::Itembe a reference, I would need a lending iterator. So instead I implemented the drivers that to some extent mimic the iterator API.coremodule to the root of the library.RepulsiveSystemtype. It is still a good idea, but it is currently a noop and I am not planning to spend time on it now. We may reintroduce it in the future.randtofastrand. It is designed to be fast (whereas in rand choosing fast generator requires conscious "effort") and has a bit simpler API. Nevertheless, still require the generator as an explicit parameter to support determinism (user sending generator initialized with a fixed seed).After all these changes are done and 0.5.0 is released, then I will migrate the whole library from nalgebra to faer.