LinearAlgebra[Modular][ChineseRemainder] - apply Garner's algorithm to reconstruct from mod m Matrix or Vector images
|
Calling Sequence
|
|
ChineseRemainder(A, m, img, prm, sto)
|
|
Parameters
|
|
A
|
-
|
current reconstruction
|
m
|
-
|
assigned name for prime product for reconstruction
|
img
|
-
|
new image, or list of new images, mod m Matrices or Vectors)
|
prm
|
-
|
new prime or list of primes
|
sto
|
-
|
(optional) temporary storage (efficiency)
|
|
|
|
|
Description
|
|
•
|
The ChineseRemainder function applies an incremental version of Garner's algorithm, updating the current image A and modulus m with the image or images specified by img and prm.
|
|
Upon successful completion, the reconstructed image is returned, and m which must be a name, is updated.
|
•
|
The A and m parameters represent the current reconstruction, and name corresponding to the current prime product.
|
|
If no reconstruction has been performed, that is, this is the first call to ChineseRemainder for this reconstruction, A and m have the values and , where n is assigned the value 1.
|
|
If the current reconstruction is to be updated with new images, A should be the Matrix or Vector returned from the prior call to ChineseRemainder, and should be the name used in the prior call.
|
|
In all cases the reconstruction is returned, even though for updates to the reconstruction ChineseRemainder works on A in-place.
|
•
|
The img and prm parameters represent the new images to be used to update the reconstruction, and the corresponding primes. For updating with a single image, these can be specified as the image and prime. For updating with multiple images, these are specified as a list of the images, and a list of the corresponding primes.
|
•
|
Regardless of the datatype of the image, the output is always datatype 'integer'.
|
|
Note: The reconstructed image is not a mod m Matrix or Vector, as it stores the entries in the symmetric range, while the input images from img are mod m Matrices or Vectors with entries in the positive range.
|
•
|
The ChineseRemainder command requires additional storage when reconstructing a result with multiple images. The ability to pre-allocate this storage and utilize it in ChineseRemainder is made available by the optional fifth argument sto. If specified, sto must be a mod m Matrix or Vector with the same datatype and dimensions as the images from img.
|
•
|
This command is part of the LinearAlgebra[Modular] package, so it can be used in the form ChineseRemainder(..) only after executing the command with(LinearAlgebra[Modular]). However, it can always be used in the form LinearAlgebra[Modular][ChineseRemainder](..).
|
|
|
Examples
|
|
Apply Chinese remainder algorithm to a Matrix, one step at a time.
>
|
|
>
|
|
| (1) |
Now reconstruct A from images.
>
|
|
| (2) |
>
|
|
| (3) |
>
|
|
| (4) |
>
|
|
| (5) |
>
|
|
| (6) |
>
|
|
| (7) |
>
|
|
| (8) |
>
|
|
| (9) |
>
|
|
| (10) |
>
|
|
| (11) |
>
|
|
| (12) |
You can do the reconstruction all at once.
>
|
|
| (13) |
>
|
|
| (14) |
>
|
|
| (15) |
Incremental reconstruction with storage (not required for first step).
>
|
|
| (16) |
>
|
|
| (17) |
>
|
|
| (18) |
>
|
|
| (19) |
Now use I1 as temp storage.
>
|
|
| (20) |
>
|
|
| (21) |
>
|
|
| (22) |
>
|
|
| (23) |
|
|