-
Notifications
You must be signed in to change notification settings - Fork 11
/
TODO_unit_tests.txt
311 lines (263 loc) · 19.8 KB
/
TODO_unit_tests.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
# TODO List related to Unit testing
This document contains a simple list of tasks related to creating unit-test programs for
various parts of the ReaK library, and noting the modules that currently do not pass some
of the unit-tests (i.e., possible bugs).
## Overall unit-test coverage:
(
N/A : Not applicable, i.e., can't really be tested (requires an explanation).
VOID : Does not exist, i.e., the unit-test does not exist yet, should be created in the future.
PART : Partial, i.e., some sub-systems have unit-tests, some are missing or failed.
PASS : Passed, i.e., the unit-test program exists and has been passed by the unit in question.
FAIL : Failed, i.e., the unit-test program exists, but the unit in question currently cannot pass it ("expected fail").
<empty-line> : it has not yet been checked if there is sufficient coverage in existing tests.
)
Core modules:
- core/base ------------------------------------------------------- N/A (too fundamental, well tested everywhere else)
- core/rtti ----------------------------------------------------- VOID (some is tested in core/serialization)
- core/serialization ---------------------------------------------- PART
- bin-archivers -------------------------------------------------- PASS
- xml-archivers -------------------------------------------------- PASS
- protobuf-archivers --------------------------------------------- PASS
- objtree-archivers ---------------------------------------------- PASS
- protobuf-schemer --------------------------------------------- VOID
- type-scheme -------------------------------------------------- VOID
- scheme-builder ----------------------------------------------- VOID
- objtree-editor ----------------------------------------------- VOID
- core/recorders -------------------------------------------------- PASS
- bin-recorder/extractor ----------------------------------------- PASS
- ssv-recorder/extractor ----------------------------------------- PASS
- tsv-recorder/extractor ----------------------------------------- PASS
- tcp-recorder/extractor ----------------------------------------- PASS
- core/sorting ---------------------------------------------------- PASS
- core/root_finders ----------------------------------------------- PASS
- bisection_method ----------------------------------------------- PASS
- secant_method -------------------------------------------------- PASS
- illinois_method ------------------------------------------------ PASS
- ford3_method --------------------------------------------------- PASS (INFORMAL) (the second best secant-style method)
- brent_method --------------------------------------------------- PASS (INFORMAL) (the best secant-style method)
- ridders_method ------------------------------------------------- PASS
- core/lin_alg ---------------------------------------------------- PART
- vect_alg ------------------------------------------------------- PASS
- vect_scalar -------------------------------------------------- VOID (a bit trivial)
- vect_view ---------------------------------------------------- VOID (a bit trivial)
- vect_index_iterator ------------------------------------------ VOID (a bit trivial)
- arithmetic_tuple --------------------------------------------- VOID
- mat_alg -------------------------------------------------------- PART
- rectangular --------------------------------------------------- PASS
- square -------------------------------------------------------- PASS
- symmetric ----------------------------------------------------- PASS
- skew-symmetric ------------------------------------------------ PASS
- identity ------------------------------------------------------ PASS
- nil ----------------------------------------------------------- PASS
- diagonal ------------------------------------------------------ PASS
- scalar ------------------------------------------------------ VOID (a bit trivial)
- permutation ------------------------------------------------- VOID (tested in mat-numerical methods)
- lower-triangular -------------------------------------------- VOID (not implemented)
- upper-triangular -------------------------------------------- VOID (not implemented)
- tri-diagonal ------------------------------------------------ VOID (not implemented)
- composite-adaptors ------------------------------------------ VOID
- views ------------------------------------------------------- VOID
- slices ------------------------------------------------------ VOID
- transpose-view ---------------------------------------------- VOID
- mat_num -------------------------------------------------------- PART
- balance ------------------------------------------------------- PASS
- balance ------------------------------------------------------ PASS
- balance_pencil ----------------------------------------------- PASS
- cholesky ------------------------------------------------------ PASS
- cholesky decomposition --------------------------------------- PASS (used in cholesky invert)
- cholesky lin-solve ------------------------------------------- PASS (used in cholesky invert)
- cholesky invert ---------------------------------------------- PASS
- band-cholesky decomposition ---------------------------------- PASS (used by band-cholesky invert)
- band-cholesky lin-solve -------------------------------------- PASS (used by band-cholesky invert)
- band-cholesky invert ----------------------------------------- PASS
- LDL decomposition -------------------------------------------- PASS (used by LDL invert)
- LDL lin-solve ------------------------------------------------ PASS (used by LDL invert)
- LDL invert --------------------------------------------------- PASS
- TriDiag-LDL decomposition ------------------------------------ PASS
- TriDiag-LDL lin-solve ---------------------------------------- PASS (used by TriDiagLDL invert)
- TriDiag-LDL invert ------------------------------------------- PASS
- controllability reduction ------------------------------------- PASS
- damped-matrix ----------------------------------------------- VOID (a bit trivial)
- matrix exponential (Padé Square-and-Sum) -------------------- VOID
- gaussian elimination ------------------------------------------ PASS
- gaussian invert ---------------------------------------------- PASS
- PLU lin-solve ------------------------------------------------ PASS (used by PLU invert)
- PLU invert --------------------------------------------------- PASS
- Givens rotations ---------------------------------------------- PASS (part of many other methods)
- Householder reflections --------------------------------------- PASS (part of QR and other methods)
- Hessenberg decompositions ------------------------------------- PASS (part of Schur decomp)
- Upper-Hessenberg decomposition ------------------------------- PASS
- Hessenberg-Triangular reduction ------------------------------ PASS (part of Gen. Real-Schur)
- Jacobi method ------------------------------------------------- PASS
- Jacobi eigen-solve ------------------------------------------- PASS
- Jacobi linlsq-solve ------------------------------------------ PASS (almost identical to pinv)
- Jacobi pseudo-invert ----------------------------------------- PASS
- QR decomposition ---------------------------------------------- PASS
- Stable-GramSchmidt orthogonalization ------------------------- PASS
- RRQR decomposition ------------------------------------------- PASS (used by controllability reduction)
- QR decomposition --------------------------------------------- PASS (used by QR pseudo-invert)
- QR linlsq-solve ---------------------------------------------- PASS (used by QR pseudo-invert)
- RRQR linlsq-solve -------------------------------------------- PASS
- RRQR linlsq-solve (rank-deficient) --------------------------- PASS
- RRQR minnorm-solve ------------------------------------------- PASS
- RRQR minnorm-solve (rank-deficient) -------------------------- PASS
- QR minnorm-solve --------------------------------------------- PASS
- R backsub ---------------------------------------------------- PASS
- QR invert ---------------------------------------------------- PASS
- QR pseudo-invert --------------------------------------------- PASS
- Schur decompositions ------------------------------------------ PASS
- Symmetric-QR eigen-solve ------------------------------------- PASS
- Symmetric-QR pseudo-invert ----------------------------------- PASS
- Symmetric-QR lin-solve --------------------------------------- PASS (used by SymQR pseudo-invert)
- Real-Schur decomposition ------------------------------------- PASS
- Generalized Real-Schur decomposition ------------------------- PASS (part of DARE/CARE solvers)
- Star product -------------------------------------------------- PASS (only wraps SVD pseudo-invert call + matrix concatenation)
- SVD decomposition --------------------------------------------- PASS
- SVD decomposition -------------------------------------------- PASS
- SVD pseudo-invert -------------------------------------------- PASS
- SVD pseudo-invert (rank-deficient) --------------------------- PASS
- SVD pseudo-invert (min-norm) --------------------------------- PASS
- SVD pseudo-invert (min-norm, rank-def) ----------------------- PASS
- Algebraic Riccati Equation (ARE) Solvers ---------------------- PASS
- Continuous-time ARE solver ----------------------------------- PASS
- inf.-horizon continuous-time (IHCT) LQR synthesis ------------ PASS (only wraps CARE algorithm)
- inf.-horizon continuous-time (IHCT) LQR with ctrl-redux ------ PASS (only wraps CARE algorithm + controllability reduction)
- inf.-horizon continuous-time (IHCT) AQR synthesis ------------ PASS (only wraps CARE algorithm)
- inf.-horizon continuous-time (IHCT) AQR with ctrl-redux ------ PASS (only wraps CARE algorithm + controllability reduction)
- inf.-horizon continuous-time (IHCT) LQG synthesis ------------ PASS (only wraps CARE algorithm)
- Discrete-time ARE solver ------------------------------------- PASS
- inf.-horizon discrete-time (IHDT) LQR synthesis -------------- PASS (only wraps DARE algorithm)
- inf.-horizon discrete-time (IHDT) LQG synthesis -------------- PASS (only wraps DARE algorithm)
- Continuous-time Spectral Factorization (CTSF) ---------------- PASS (identical to CARE)
- Discrete-time Spectral Factorization (DTSF) ------------------ PASS (identical to DARE)
- core/kinetostatics ---------------------------------------------- PART
- 2D rotations / transforms -------------------------------------- PASS
- 3D rotations / transforms -------------------------------------- PASS
- quaternionic algebra ------------------------------------------- PASS
- generalized coordinates -------------------------------------- VOID (might be too trivial to require tests, almost POD-types)
- 2D kinetostatic frames --------------------------------------- VOID
- 3D kinetostatic frames --------------------------------------- VOID
- motion jacobians --------------------------------------------- VOID
- core/integrators ---------------------------------------------- VOID (have been tested in the past, and when using KTEs)
- Euler integrator
- Midpoint integrator
- Runge-Kutta-4 integrator
- Runge-Kutta-5 integrator
- Fehlberg 4-5 integrator
- Dormand-Prince 4-5 integrator
- Adams-Bashforth-Moulton 3 integrator
- Adams-Bashforth-Moulton 5 integrator
- Modified Hamming Method integrator
- Iterated Modified Hamming Method integrator
- core/optimization ------------------------------(INFORMAL)----- VOID (have been tested quite a bit, but no formal unit-tests)
- Augmented Lagrangian methods ------------------------------- FAIL (sometimes slowly makes it to a solution, but usually fails, this is somewhat expected, it is a bad method)
- without constraints
- with equality contraints
- with inequality contraints
- with inequality-equality contraints
- Conjugate Gradient methods
- linear conjugate gradient
- non-linear conjugate gradient with Fletcher-Reeves
- non-linear conjugate gradient with Polak-Ribiere
- non-linear conjugate gradient with Hestenes-Stiefel
- non-linear conjugate gradient with Dai-Yuan
- non-linear conjugate gradient with Hager-Zhang
- Gauss-Newton method (quadratic stepping) ----------------------- PASS (INFORMAL) (very reliable, very accurate)
- Gauss-Newton non-linear least-square -------------------------- PASS (INFORMAL)
- Gauss-Newton non-linear least-square with bounds -------------- PASS (INFORMAL)
- Jacobian-transpose method (steepest-descent) --------------- FAIL (somewhat expected, this is a bad method)
- Jacobian-transpose non-linear least-square ---------------- FAIL
- Jacobian-transpose non-linear least-square with bounds ---- FAIL
- Levenberg-Marquardt methods (non-lin. least-square) ------------ PASS (INFORMAL) (fails on some difficult cases, lacks precision compared to Gauss-Newton)
- without bounds ------------------------------------------------ PASS (INFORMAL)
- with bounds --------------------------------------------------- PASS (INFORMAL)
- Line-search methods
- Dichotomous search -------------------------------------------- PASS (INFORMAL)
- Golden-section search ----------------------------------------- PASS (INFORMAL)
- Fibonacci search ---------------------------------------------- PASS (INFORMAL)
- Back-tracking search ---------------------------------------- VOID (part of many "line-search" methods)
- Expand-and-zoom search -------------------------------------- VOID (part of many "line-search" methods)
- Mehrotra's method (interior-point predictor-corrector) --------- PART
- Mehrotra's Linear-Prog. method ------------------------------ VOID
- Mehrotra's Quadratic-Prog. method ----------------------------- PASS (INFORMAL)
- Nelder-Mead method (gradient-less, simplex-method)
- Newton methods
- Line-search Newton method
- Line-search regulated Newton method
- Line-search bounded Newton method
- Line-search bounded regulated Newton method
- Trust-region Newton method
- Trust-region regulated Newton method
- Trust-region bounded Newton method
- Trust-region bounded regulated Newton method
- Non-linear Interior-point methods (penalty-barrier, SQP) --- FAIL
- Line-search NLIP Newton method ---------------------------- FAIL (the issue seems to be numerical stability, the solution seems to be dragged towards ill-conditioned areas and then fails)
- Line-search NLIP Quasi-Newton(BFGS) method ---------------- FAIL
- Trust-region NLIP Newton method --------------------------- FAIL (INFORMAL) (works well on some problems, fails in many)
- Trust-region NLIP Quasi-Newton(SR-1) method --------------- FAIL (INFORMAL) (works well on some problems, fails in many)
- Quadratic-programming algorithms
- Null-space QP method ------------------------------------------ PASS (INFORMAL)
- Null-space Rank-revealing QP method ------------------------- VOID
- Projected Conjugate-Gradient method --------------------------- PASS (INFORMAL)
- Quasi-Newton methods (unconstrained)
- BFGS method
- Bounded BFGS method
- DFP method
- Bounded DFP method
- Broyden-class method
- Bounded Broyden-class method
- Symmetric Rank-1 method (trust-region)
- Bounded Symmetric Rank-1 method (trust-region)
- Sequential Quadratic-programming methods ----------------------- PASS (INFORMAL) (the most consistent NLP methods, but only for equality constraints)
- Byrd-Omojokun SQP Newton method ------------------------------- PASS
- Byrd-Omojokun SQP Quasi-Newton(SR-1) method ------------------- PASS
- Simplex method (linear-programming) -------------------------- VOID
- core/tensors -------------------------------------------------- VOID (not implemented, only rough drafts)
Multi-body dynamics modules:
- ctrl/mbd_kte
- ctrl/kte_models
Control and estimation modules:
- ctrl/ctrl_sys
- ctrl/sys_integrators
Graph-algorithmic modules:
- ctrl/graph_alg
Path-planning modules:
- ctrl/interpolation
- ctrl/topologies
- ctrl/path_planning
- ctrl/heuristics ----------------------------------------------- VOID (not implemented, only rough drafts)
## Notable issues in existing unit-tests:
The secant_method seems to be unstable and very prone to divergence from the solution. This is
odd considering that most other methods (that do work well), except for bisection, are variants
of the same algorithm. There might a simple little bug in it. It also seems to diverge quickly,
in a few iterations, but it does, however work sometimes, indicating that it is somewhat working.
The shell_sort method does not work. I don't really care to fix it, so, that's all I have to say about that.
In mat_num:
The Jacobi methods don't work, i.e., the pseudoinvert_Jacobi function and eigensolve_Jacobi function.
There are better alternatives in the library already (SymQR, QR-alg, and SVD) that solve the same problem,
so this is not such a high-priority. It would be nice to investigate a bit. The Jacobi method
implementations also seem to be rather slow (i.e., they should perform equal to the QR algorithms or faster,
but instead, are more comparable to SVD, which is a much slower (heavy-duty) algorithm). The method
probably needs a full revision (similar to the full revision done on the QR algorithms a while back).
The decompose_PLTLP function does not work.
The decompose_TriDiagLDL function does not work.
These are just things that I implemented on the side for no real purpose. It would be nice to fix them,
and they are certainly very simple, but they have low priority due to not really being useful for anything
that I know of.
CARE / DARE methods technically pass all the unit-tests, but to be honest, some of the more difficult
test cases have been excluded from the test-suite. The test-suite currently contains a representative
sample of typical problems and the methods implemented seem to solve those fairly well, although the
precision is not as good as in reported literature. The implementations are quite experimental in the
sense that they are not robust to edge-cases (e.g., ill-conditioning, singular problems, un-controllable but
stabilizable systems, etc.), they tend to fail (by throwing a singularity exception) a bit too often, or
loss of precision can be significant. This algorithm is one of the most complicated
matrix numerical method that exists, and after some research, I have been led to believe that there exists
only one other implementation of this algorithm in the world, accessible as Slicot's "SB02OD" routine,
which is the Fortran77 implementation by the original authors of the algorithm and its
variants in the early 80s, every other mathematical software that provides Riccati equation solvers
are known to use that very same implementation (e.g., Matlab, Octave, etc.). So, obviously, it seems
that developing an original and robust implementation of this algorithm is a task that very few people,
if any, have attempted, and I can understand why, this is a very difficult algorithm to implement.
And it is thus not so surprising that my original implementation is still lacking a bit
in terms of robustness, but it is certainly usable for many "normal" problems (fairly small
and well-conditioned matrices, and without too strict requirements on final precision).