Ticket #22970: benchmark_matrices.py

File benchmark_matrices.py, 6.6 KB (added by vdelecroix, 3 years ago)
Line 
1r"""
2File to benchmark the code from
3
4     https://trac.sagemath.org/ticket/22970
5
6
7To benchmark, just run::
8
9    sage: test_echelonize()
10    sage: test_determinant()
11    sage: test_charpoly()
12"""
13from timeit import timeit
14
15def low_rank_random_matrix(nrows, ncols, rank, bound=10, density=1.0):
16    return random_matrix(QQ, nrows, rank, num_bound=bound, den_bound=bound, density=density) * \
17           random_matrix(QQ, rank, ncols, num_bound=bound, den_bound=bound, density=density)
18
19
20def test_echelonize():
21    r"""
22    EXAMPLES::
23
24        sage: test_echelonize()
25        nrows=3  ncols=3  rank=3, density=0.8889 nbits(height)=3
26        flint        0.0076
27        multimodular 0.3418
28        padic        0.3673
29
30        nrows=5  ncols=5  rank=5, density=1.0000 nbits(height)=100
31        flint        0.0565
32        multimodular 0.3284
33        padic        0.5626
34
35        nrows=10  ncols=10  rank=5, density=1.0000 nbits(height)=37
36        flint        0.1063
37        multimodular 2.6420
38        padic        7.6511
39
40        nrows=10  ncols=10  rank=10, density=1.0000 nbits(height)=200
41        flint        10.1606
42        multimodular 1.5586
43        padic        2.1540
44
45        nrows=100  ncols=100  rank=20, density=0.1799 nbits(height)=12
46        flint        9.1834
47        multimodular 12.2192
48        padic        74.8152
49
50        nrows=100  ncols=100  rank=100, density=0.2598 nbits(height)=2
51        flint        1.0603
52        multimodular 2.5480
53        padic        4.0739
54
55        nrows=100  ncols=100  rank=100, density=0.3946 nbits(height)=2
56        flint        1.0586
57        multimodular 2.5404
58        padic        4.2653
59
60        nrows=100  ncols=100  rank=100, density=1.0000 nbits(height)=2
61        flint        1.2092
62        multimodular 2.8951
63        padic        4.6248
64    """
65    m = random_matrix(QQ, 3, num_bound=5, den_bound=5)
66    benchmark_echelonize(m, 200)
67
68    m = random_matrix(QQ, 5, num_bound=2**100, den_bound=2**100)
69    benchmark_echelonize(m, 200)
70
71    m = low_rank_random_matrix(10, 10, 5, bound=50)
72    benchmark_echelonize(m, 100)
73
74    m = random_matrix(QQ, 10, 10, num_bound=2**200, den_bound=2**200)
75    benchmark_echelonize(m, 10)
76
77    m = low_rank_random_matrix(100, 100, 20, density=0.1)
78    benchmark_echelonize(m, 10)
79
80    m = random_matrix(QQ, 100, 100, density=0.3)
81    benchmark_echelonize(m, 10)
82
83    m = random_matrix(QQ, 100, 100, density=0.5)
84    benchmark_echelonize(m, 10)
85
86    m = random_matrix(QQ, 100, 100, density=1.0)
87    benchmark_echelonize(m, 10)
88
89
90def benchmark_echelonize(m, number):
91    r"""
92    For echelon form one can choose between:
93
94    - flint
95    - padic
96    - multimodular
97    (- classical: not tested always slower)
98    """
99    print("nrows=%d  ncols=%d  rank=%d, density=%.4f nbits(height)=%d" %(m.nrows(), m.ncols(), m.rank(), float(m.density()), m.height().nbits()))
100    src = "m.echelon_form(algorithm='{algo}'); m._clear_cache()"
101    setup = 'from sage.all import matrix, ZZ, QQ\nm = {}'.format(sage_input(m, preparse=False))
102    for algo in ['flint', 'multimodular', 'padic']:
103        print '%-12s %.4f' % (algo, 1000 * timeit(src.format(algo=algo), setup=setup, number=number) / number)
104    print
105
106
107def test_determinant():
108    r"""
109    EXAMPLES::
110
111        sage: test_determinant()
112        dim=3 density=0.7778 nbits(height)=3
113        flint        0.0092
114        integer      0.1334
115        pari         0.0017
116
117        dim=3 density=1.0000 nbits(height)=100
118        flint        0.0113
119        integer      0.1188
120        pari         0.0269
121
122        dim=10 density=0.2600 nbits(height)=4
123        flint        0.0098
124        integer      0.1098
125        pari         0.0020
126
127        dim=30 density=1.0000 nbits(height)=5
128        flint        0.9006
129        integer      1.0754
130        pari         34.5452
131
132        dim=30 density=0.2544 nbits(height)=5
133        flint        0.4389
134        integer      0.9986
135        pari         179.9622
136    """
137    m = random_matrix(QQ, 3, num_bound=5, den_bound=5)
138    benchmark_determinant(m, 500)
139
140    m = random_matrix(QQ, 3, num_bound=2**100, den_bound=2**100)
141    benchmark_determinant(m, 200)
142
143    m = random_matrix(QQ, 10, num_bound=10, den_bound=16, density=0.3)
144    benchmark_determinant(m, 100)
145
146    m = random_matrix(QQ, 30, num_bound=10, den_bound=16, density=1.0)
147    benchmark_determinant(m, 10)
148
149    m = random_matrix(QQ, 30, num_bound=10, den_bound=16, density=0.3)
150    benchmark_determinant(m, 10)
151
152
153def benchmark_determinant(m, number=10):
154    r"""
155    - flint
156    - pari
157    - integer
158    """
159    print("dim=%d density=%.4f nbits(height)=%d" % (m.nrows(), m.density(), m.height().nbits()))
160    src = "m.determinant(algorithm='{algo}'); m._clear_cache()"
161    setup = 'from sage.all import matrix, ZZ, QQ\nm = {}'.format(sage_input(m, preparse=False))
162    for algo in ['flint', 'integer', 'pari']:
163        print '%-12s %.4f' % (algo, 1000 * timeit(src.format(algo=algo), setup=setup, number=number) / number)
164    print
165
166def test_charpoly():
167    r"""
168    EXAMPLES::
169
170        sage: test_charpoly()
171        dim=3 density=0.7778 nbits(height)=2
172        flint        0.3875
173        linbox       1.3019
174        generic      0.0431
175
176        dim=4 density=0.5625 nbits(height)=2
177        flint        0.1776
178        linbox       1.2013
179        generic      0.0450
180
181        dim=5 density=0.6400 nbits(height)=2
182        flint        0.1737
183        linbox       1.2952
184        generic      0.0532
185
186        dim=6 density=0.6111 nbits(height)=2
187        flint        0.1850
188        linbox       1.2773
189        generic      0.0651
190
191        dim=10 density=0.4100 nbits(height)=2
192        flint        0.2343
193        linbox       1.4250
194        generic      0.1818
195
196        dim=10 density=1.0000 nbits(height)=2
197        flint        0.2521
198        linbox       1.4264
199        generic      0.4842
200
201        dim=30 density=0.0978 nbits(height)=2
202        flint        1.4168
203        linbox       6.1872
204        generic      7.1217
205
206        dim=30 density=0.4000 nbits(height)=2
207        flint        2.9982
208        linbox       3.1161
209        generic      23.8294
210
211        dim=30 density=1.0000 nbits(height)=2
212        flint        4.8531
213        linbox       3.4320
214        generic      50.0362
215    """
216    m = random_matrix(QQ, 3)
217    benchmark_charpoly(m, 100)
218    m = random_matrix(QQ, 4)
219    benchmark_charpoly(m, 100)
220    m = random_matrix(QQ, 5)
221    benchmark_charpoly(m, 100)
222    m = random_matrix(QQ, 6)
223    benchmark_charpoly(m, 100)
224
225    m = random_matrix(QQ, 10, density=0.5)
226    benchmark_charpoly(m, 100)
227
228    m = random_matrix(QQ, 10, density=1.0)
229    benchmark_charpoly(m, 100)
230
231    m = random_matrix(QQ, 30, density=0.1)
232    benchmark_charpoly(m, 100)
233
234    m = random_matrix(QQ, 30, density=0.5)
235    benchmark_charpoly(m, 100)
236
237    m = random_matrix(QQ, 30, density=1.0)
238    benchmark_charpoly(m, 100)
239
240
241def benchmark_charpoly(m, number=10):
242    r"""
243    - flint
244    - linbox
245    - generic
246    """
247    print("dim=%d density=%.4f nbits(height)=%d" % (m.nrows(), m.density(), m.height().nbits()))
248    src = "m.charpoly(algorithm='{algo}'); m._clear_cache()"
249    setup = 'from sage.all import matrix, ZZ, QQ\nm = {}'.format(sage_input(m, preparse=False))
250    for algo in ['flint', 'linbox', 'generic']:
251        print '%-12s %.4f' % (algo, 1000 * timeit(src.format(algo=algo), setup=setup, number=number) / number)
252    print