Mantis - ISSUES

0000404: FIXED: minor bugs in Spline1D subpackage

Fixed two bugs:
* Spline1DLinTransX() did not correctly handled non-smooth (piecewise linear) splines
* Spline1DBuildCubic() with periodic boundary conditions did not correctly handled input data with omitted last Y value (rare case, but should be handled correctly)

0000413: RMatrixEVD incorrectly calculates eigenvectors of the large matrix

See attachment and http://forum.alglib.net/viewtopic.php?f=2&t=490 for more info

0000430: IMPLEMENTED: RBF model

RBF model for interpolation in 2 and 3-dimensional spaces, which:
* supports Gaussian RBF's with additional linear term
* supports scattered interpolation, but current version requires approximately uniform distribution of points (no outliers or clustering)
* supports interpolation of scalar and vector functions
* can calculate function values at arbitrary points and on regular grids
* supports serialization
* uses efficient O(N*logN) algorithms to build model, suited for interpolation of very large datasets (100000 points and even more)

0000431: Improved RBF

Possible improvements:

1. Non-smoothness penalty, similar to one used for cubic spline fitting. Can be very costly...

2. Regularized solution, can be good for problems with not-well-separated points. We generate ACBF's as usual, but solve linear problem with quite large value of regularization coefficient - from 0.01*max(y) to 1.00*max(y). We can perform several steps of iterative improvement.

Such algorithm should allow us to work with quite large fixed radii. And maybe, to work with non-distinct noisy data. At least, I hope that it will do - no one knows for sure...

Note: we may need to carefully filter centers used to build approximate cardinal basis function. Maybe we will have to apply regularization in the ACBF construction too (non-distinct points => ill conditioned systems).

3. QNN algorithm with filtering for radius values

0000445: TWEAK: support for empty KD-trees

Added support for zero-sized KD-trees, i.e. trees which were built from zero dataset.

0000442: Efficiently handle zero elements during triangular/orthogonal factorization

Dense Level 2 LU/QR/... performance on sparse matrices stored in the dense form can be significantly improved.

The idea is to skip rows of rank-1 updates which have zero coefficients. It can be done with just one "if", its cost is insignificant, and it can have major performance consequences on some types of the matrices.

0000441: Exception handling demos for doctests

doctests must include demos of exception handling

0000440: Multilayered RBF interpolants

Two layers:
* first one, uniform grid of RBF's, non-smoothness penalty.
* second one, R-NN approach (radius is equal to distance to NN)

0000439: Large-scale memory allocations in C++

The problem: large-scale memory allocations don with malloc() may fail under Windows, even when we work in a 64-bit environment.

Solution: to implement memory allocations for large (beyond 1 MB) arrays:
* using VirtualAlloc - under Windows
* using ????? - under *nix (not investigates this behaviour under *nix, may be there is not problem with malloc under *nix).

0000438: Refactoring of the BLEIC optimizer

Use new functions provided by the _optserv.ap unit, switch to planned constrained preconditioner functions.

0000420: FIXED: BLEIC optimizer can fail when started from infeasible point

Feasibility solver used by BLEIC had flaw in the algorithm which prevented it from finding feasible points in some circumstances. It was replaced by better algorithm with guaranteed convergence (unless problem is so ill-conditioned that it is impossible to find feasible point because of rounding errors).

0000437: Feasibility solver

Solver which finds feasible point subject to boundary and linear constraints:
* two forms - canonical (A*x=b) and general BLEIC constraints
* may be, solver for a problem with general (nonlinear) constraints
* scaling of the inputs and constraint matrix
* use LQ or bidiagonalization instead of SVD. Or, maybe, orthogonalization for rows of the matrix...

0000436: Minor issue in MLPETrain()

Multiple restarts do not improve solution.

0000435: IMPLEMENTED: sparse LSQR solver

Sparse solver which works with matrices represented by SparseMatrix structure and can solve:
* square non-symmetric non-degenerate problems
* non-square non-degenerate problems (least squares solution is returned)

This solvers avoid squaring of condition number when working with least squares problem. Thus, it is better suited for solution of least squares problems than CG on normal equations. However, algorithm should be used with caution on rank-deficient or ill conditioned problems.

0000434: IMPLEMENTED: sparse linear CG optimizer

Sparse linear CG optimizer, which works with matrices stored in the SparseMatrix structure.

0000410: IMPLEMENTED: sparse matrices

Sparse matrix structure which supports:
* improved CRS format (for memory efficient operations) and Hash-Table representation (easy to use format, intended to simplify matrix creation)
* basic operations with elements: Set, Get, Add
* linear matrix-vector operations: A*x, A'*x, simultaneous calculation of both products
* linear matrix-matrix operations
* operations with symmetric matrices given by lower or upper triangle only

0000403: IMPLEMENTED: separate functions for mean, variance, standard deviation

Separate functions for calculations of mean, variance and standard deviation. See http://forum.alglib.net/viewtopic.php?f=2&t=452 for rationale.

0000433: IMPLEMENTED: generation of random values from continuous/discrete distribution given by finite samples

Two new functions - HQRNDDiscrete and HQRNDContinuous - which can be used to generate random values from continuous/discrete distribution given by finite samples.

0000432: IMPLEMENTED: SMA, EMA, LRMA filters

Filters used to smooth variations in time series data:
* simple moving averages
* exponential moving averages
* linear regression moving averages

0000429: Acceleration support for LM optimizer

Return it back, now using BLEIC optimizer for inner preconditioned iterations.

This feature requires remastering of the BLEIC/CG optimizers - CG must support equality constrained preconditioning (i.e. preconditioner which respects equality constraints).

0000428: Better support for lambda functions

C++ and C# versions of ALGLIB must be able to accept lambda functions as their parameters. As for C++, we may need to accept std::function.

Doctests may need modification...

0000427: Checks for correctness of user-supplied gradient

Optional, should be turned on explicitly.

0000426: Automatic differentiation in NLEQ solver

Like it was implemented in L-BFGS and others.

0000425: Optimized k-NN queries for 2D and 3D

* tightly optimized code, special code for 2D, special code for 3D
* thread-safe code

0000424: Sparse GMRES for least squares

GMRES for sparse linear least squares, like described in www.nii.ac.jp/TechReports/07-009E.pdf and www.nii.ac.jp/TechReports/04-006E.pdf