ASKSAGE: Sage Q&A Forum - Latest question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 06 Aug 2020 06:08:00 -0500parallel matrix rankhttps://ask.sagemath.org/question/52889/parallel-matrix-rank/ I have* a (relatively) large non-square symbolic matrix $M$ which I would like to calculate the rank of. The entries of the matrix are polynomials with coefficients in a (small) finite field, and the matrix is relatively sparse, although currently it's being treated as a non-sparse matrix.
The rank could simply be calculated as `M.rank()`, but I'm not sure whether or not the matrix rank algorithm implemented works in parallel or not. Could someone clarify whether or not parallel calculation of matrix rank is implemented in Sage or not? If it is implemented but isn't used by default, how do I make use of the parallel version?
Thanks!
(*) It's more accurate to say that I'm *going to have* such a matrix; my initial version of the code was written in Mathematica, and I'm currently porting the code to Sage after too many headaches with Mathematica's handling of finite fields, which could definitely be improved upon. So unfortunately I'm not yet at the stage of running `M.rank()` and checking whether or not it runs in parallel.BakerbakuraThu, 06 Aug 2020 06:08:00 -0500https://ask.sagemath.org/question/52889/Parallelizing symbolic matrix*vector computations for sparse matrices and vectorshttps://ask.sagemath.org/question/51560/parallelizing-symbolic-matrixvector-computations-for-sparse-matrices-and-vectors/Hi everyone,
I am currently running computations which involve a lot of operations of the type matrix*vector, where both objects are sparse and the result can be expected to be sparse as well. The matrices' base field is the symbolic ring. If I drop certain normalizations I could also work over QQ, I think.
The above operations appear sequentially. Although there are some options for parallelizing these at least in part, the biggest acceleration would be achieved if the multiplication itself could be parallelized. Is there a way to do this in Sage?
Greetings and thank you very much.
Edit: Work in progress
Below I put some code that I produced so far which is very far from a solution but produces new slow-downs that I do not understand. The strategy is to save a sparse matrix by its nonzero rows which is facilitated by the following code snippet:
def default_to_row(M):
rows_of_M=M.rows()
relevant=[]
for r in range(len(rows_of_M)):
row=rows_of_M[r]
if dot_sparse(row,row)!=0:
relevant.append([r,row])
return relevant
The row*vector multiplications are facilitated by the function
# indexed_row of type [i,v] where v is a sparse vector and i is
# the row in the matrix it corresponds to.
def mult_sparse(indexed_row,v2):
res=0
for k in indexed_row[1].dict():
res=res+indexed_row[1][k]*v2[k]
return [indexed_row[0],res]
and regular vector multiplication is given by
def dot_sparse(v,w):
res=0
for k in v.dict():
res=res+v[k]*w[k]
return res
Now to the actual benchmarks:
import concurrent.futures
import time
import itertools
dim=5000
M=random_matrix(QQ,nrows=dim,ncols=dim,sparse=True,density=0.0001)
M_by_rows=default_to_row(M)
v=vector(QQ,dim,list(range(dim)),sparse=True)
print(len(M_by_rows))
Using the concurrent.futures library yields the following performance:
start = time.perf_counter()
with concurrent.futures.ProcessPoolExecutor() as executor:
start2 = time.perf_counter()
results = executor.map(mult_sparse,M_by_rows,itertools.repeat(v) )
finish2 = time.perf_counter()
coefficients={}
for result in results:
if result[1]!=0:
coefficients[result[0]]=result[1]
new_v=vector(QQ,v.degree(),coefficients,sparse=True)
finish = time.perf_counter()
print(f'Finished in {round(finish-start, 2)} seconds with Pooling.')
print(f'The executor alone took {round(finish2-start2, 2)} seconds.')
where the dimensions are adjusted so that the computation does not exceed my RAM capacities because every spawned subprocess takes copies (at least of v). A comparison with serial approaches, both the standard one and the serial version of my particular straegy, show that the parallel version is significantly slower (18 and 7 seconds in the above outputs) while the serial versions do not differ (0.02 seconds in both cases):
start = time.perf_counter()
new_v=M*v
finish = time.perf_counter()
print(f'Finished in {round(finish-start, 2)} second(s) for the regular computation')
start = time.perf_counter()
coefficients={}
for row in M_by_rows:
coefficients[row[0]]=mult_sparse(row,v)[1]
new_v=vector(QQ,v.degree(),coefficients,sparse=True)
finish = time.perf_counter()
print(f'Finished in {round(finish-start, 2)} second(s) in a serial computation')
print(f'Check if the vectors coincide:')
test=new_v-M*v
n=dot_sparse(test,test)
if n==0:
print(True)
else:
print(False)Robin_FTue, 26 May 2020 11:00:39 -0500https://ask.sagemath.org/question/51560/Python MultiProcessing module stuck for long outputshttps://ask.sagemath.org/question/51533/python-multiprocessing-module-stuck-for-long-outputs/I am using SageMath 9.0 and I tried to do paralle computation in two ways
1) parallel decoration built in SageMath;
2) the MultiProcessing module of Python.
When using paralell decoration, everything works fine. When using MultiProcessing module for the same problem with the same input, everything works fine for short output, but there is a problem when the output is long. SageMath gets stuck after the computation if the output is long. I monitored the CPU usage, it peaks at first and then returns to zero, which means that the computation is complete. However, the output still does not appear.
What puzzles me is that the problem depends on the length of output, not the time of computation. For the same computation, once I add a line to manually set the output to be something short, or extract a small part of the original output, then the computation no longer gets stck in the end, and that small part agrees with the original answer.
I would like to know if there is any hidden parameter to prevent the Python MultiProcessing module from producing long outputs in Sagemath.
P.S. Following the suggestion of @tmonteil, I attached my code with an example.
def f(n):
return 2 ^ (n ^ n)
def g(n):
return factor(2 ^ (n ^ n))
def run(function, parameters):
from multiprocessing import Process, Queue
def target_function(x, queue):
queue.put(function(*x))
results = list()
if __name__ == "__main__":
queue = Queue()
processes = [Process(target=target_function, args=(i, queue)) for i in parameters]
for p in processes:
p.start()
for p in processes:
p.join()
results = [queue.get() for p in processes]
return results
On my computer, the command
run(f,[(3,),(4,),(5,),(6,)])
works fine but the command
run(f,[(7,)])
gets stuck. On the other hand, the command
run(g,[(3,),(4,),(5,),(6,),(7,),(8,),(9,),(10,)])
works fine. Note that the function g does strictly more jobs than f, but its answers are much shorter.dzhy444Sun, 24 May 2020 08:38:40 -0500https://ask.sagemath.org/question/51533/getting RESetMapReduce to use multiple coreshttps://ask.sagemath.org/question/50208/getting-resetmapreduce-to-use-multiple-cores/I am reading the [documentation](https://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html#protocol-description) on how to parallelize recursive-enumeration computations, and I cannot for the life of me get `RESetMapReduce` to use more than one core of my machine.
I am using the example immediately before the bulleted item titled **Generating series** on that page, with a minor modification:
sage: from sage.parallel.map_reduce import RESetMapReduce
sage: S = RESetMapReduce(
....: roots=[[]],
....: children=lambda l: [l + [0], l + [1]] if len(l) < 32 else [],
....: map_function=lambda x: 1,
....: reduce_function=lambda x, y: x + y,
....: reduce_init=0)
sage: S.run()
I changed the length to 32 to make the computation heftier. If I run this and watch the process with `htop` I can see it using only one of my 8 cores to `100%` capacity, ignoring the others.
I have even tried passing the argument `max_proc=8` to the `.run()` method, to no effect.grobberMon, 09 Mar 2020 22:05:58 -0500https://ask.sagemath.org/question/50208/Parallel computation for different functionshttps://ask.sagemath.org/question/50013/parallel-computation-for-different-functions/For a single function with a list of inputs, the @parallel decoration can be used to do parallel computation. I am wandering whether it is possible to do parallel computation for different functions.
A simple is example is to calculate the difference f-g of two independent functions f and g. How can I ask SageMath to simultaneously compute the values of f and g, and then calculate the difference?
My time measurements suggest that when calculating the difference f-g, SageMath actually calculates f and g one after another, and then take the difference.
I can think of a naive approach using the @parallel decoration. I can create a function whose input variable is the name of the functions I want to compute simultaneously. Then I use a list of function names as input to get a generator of outputs. This may work if the final result doesn't depend on the order of the outputs, but does not work if the order matters, for example when taking the difference.
In general, suppose I have a flow chart for the computation, in other words, I already know which jobs can be parallelized and how the information flows to the next stage. Then what is the best way to implement the flow chart?dzhy444Fri, 21 Feb 2020 01:37:16 -0600https://ask.sagemath.org/question/50013/Cython problem with map-reducehttps://ask.sagemath.org/question/46839/cython-problem-with-map-reduce/Below some minimal code using map-reduce:
# %attach SAGE/test.spyx
from sage.parallel.map_reduce import RESetMapReduce
cpdef test(int n):
S = RESetMapReduce(roots = [[]],children = lambda l: [l+[0], l+[1]] if len(l) <= n else [],map_function = lambda x : 1,reduce_function = lambda x,y: x+y,reduce_init = 0)
return S.run()
whose compilation reveals a Cython problem `Error compiling Cython file` , `AttributeError: 'ClosureScope' object has no attribute 'scope_class'`, see below:
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 8.3, Release Date: 2018-08-03 │
│ Type "notebook()" for the browser-based notebook interface. │
│ Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
sage: %attach SAGE/test.spyx
Compiling ./SAGE/test.spyx...
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
<ipython-input-1-506a10c79ce0> in <module>()
----> 1 get_ipython().magic(u'attach SAGE/test.spyx')
/opt/sagemath-8.3/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in magic(self, arg_s)
2158 magic_name, _, magic_arg_s = arg_s.partition(' ')
2159 magic_name = magic_name.lstrip(prefilter.ESC_MAGIC)
-> 2160 return self.run_line_magic(magic_name, magic_arg_s)
2161
2162 #-------------------------------------------------------------------------
/opt/sagemath-8.3/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in run_line_magic(self, magic_name, line)
2079 kwargs['local_ns'] = sys._getframe(stack_depth).f_locals
2080 with self.builtin_trap:
-> 2081 result = fn(*args,**kwargs)
2082 return result
2083
<decorator-gen-115> in attach(self, s)
/opt/sagemath-8.3/local/lib/python2.7/site-packages/IPython/core/magic.pyc in <lambda>(f, *a, **k)
186 # but it's overkill for just that one bit of state.
187 def magic_deco(arg):
--> 188 call = lambda f, *a, **k: f(*a, **k)
189
190 if callable(arg):
/opt/sagemath-8.3/local/lib/python2.7/site-packages/sage/repl/ipython_extension.pyc in attach(self, s)
156 sage: shell.quit()
157 """
--> 158 return self.shell.ex(load_wrap(s, attach=True))
159
160 @line_magic
/opt/sagemath-8.3/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in ex(self, cmd)
2421 """Execute a normal python statement in user namespace."""
2422 with self.builtin_trap:
-> 2423 exec(cmd, self.user_global_ns, self.user_ns)
2424
2425 def ev(self, expr):
<string> in <module>()
/opt/sagemath-8.3/local/lib/python2.7/site-packages/sage/repl/load.pyc in load(filename, globals, attach)
265 if attach:
266 add_attached_file(fpath)
--> 267 exec(load_cython(fpath), globals)
268 elif ext == '.f' or ext == '.f90':
269 from sage.misc.inline_fortran import fortran
/opt/sagemath-8.3/local/lib/python2.7/site-packages/sage/repl/load.pyc in load_cython(name)
65 """
66 from sage.misc.cython import cython
---> 67 mod, dir = cython(name, compile_message=True, use_cache=True)
68 import sys
69 sys.path.append(dir)
/opt/sagemath-8.3/local/lib/python2.7/site-packages/sage/misc/cython.pyc in cython(filename, verbose, compile_message, use_cache, create_local_c_file, annotate, sage_namespace, create_local_so_file)
636 You can fix your code by adding "from {} cimport {}".
637 """.format(pxd, name))
--> 638 raise RuntimeError(cython_messages.strip())
639
640 if verbose >= 0:
RuntimeError: Error compiling Cython file:
------------------------------------------------------------
...
# %attach SAGE/test.spyx
from sage.parallel.map_reduce import RESetMapReduce
cpdef test(int n):
^
------------------------------------------------------------
_home_sage_SAGE_test_spyx_0.pyx:5:6: closures inside cpdef functions not yet supported
Error compiling Cython file:
------------------------------------------------------------
...
# %attach SAGE/test.spyx
from sage.parallel.map_reduce import RESetMapReduce
cpdef test(int n):
S = RESetMapReduce(roots = [[]],children = lambda l: [l+[0], l+[1]] if len(l) <= n else [],map_function = lambda x : 1,reduce_function = lambda x,y: x+y,reduce_init = 0)
^
------------------------------------------------------------
_home_sage_SAGE_test_spyx_0.pyx:6:44: Compiler crash in CreateClosureClasses
ModuleNode.body = StatListNode(_home_sage_SAGE_test_spyx_0.pyx:3:0)
StatListNode.stats[1] = CFuncDefNode(_home_sage_SAGE_test_spyx_0.pyx:5:6,
args = [...]/1,
modifiers = [...]/0,
needs_closure = True,
overridable = 1,
visibility = u'private')
CFuncDefNode.body = StatListNode(_home_sage_SAGE_test_spyx_0.pyx:6:1,
is_terminator = True)
StatListNode.stats[0] = SingleAssignmentNode(_home_sage_SAGE_test_spyx_0.pyx:6:19)
SingleAssignmentNode.rhs = GeneralCallNode(_home_sage_SAGE_test_spyx_0.pyx:6:19,
is_temp = 1,
result_is_used = True,
use_managed_ref = True)
GeneralCallNode.keyword_args = DictNode(_home_sage_SAGE_test_spyx_0.pyx:6:20,
is_dict_literal = True,
is_temp = 1,
obj_conversion_errors = [...]/0,
reject_duplicates = True,
result_is_used = True,
use_managed_ref = True)
DictNode.key_value_pairs[1] = DictItemNode(_home_sage_SAGE_test_spyx_0.pyx:6:33,
result_is_used = True,
use_managed_ref = True)
DictItemNode.value = LambdaNode(_home_sage_SAGE_test_spyx_0.pyx:6:44,
args = [...]/1,
binding = True,
is_temp = 1,
lambda_name = 'lambda',
name = u'<lambda>',
needs_closure = True,
needs_self_code = True,
pymethdef_cname = u'__pyx_mdef_27_home_sage_SAGE_test_spyx_0_4test_lambda',
result_is_used = True,
use_managed_ref = True)
Compiler crash traceback from this point on:
File "Cython/Compiler/Visitor.py", line 180, in Cython.Compiler.Visitor.TreeVisitor._visit
return handler_method(obj)
File "/opt/sagemath-8.3/local/lib/python2.7/site-packages/Cython/Compiler/ParseTreeTransforms.py", line 2764, in visit_LambdaNode
self.create_class_from_scope(node.def_node, self.module_scope, node)
File "/opt/sagemath-8.3/local/lib/python2.7/site-packages/Cython/Compiler/ParseTreeTransforms.py", line 2713, in create_class_from_scope
func_scope.scope_class = cscope.scope_class
AttributeError: 'ClosureScope' object has no attribute 'scope_class'Sébastien PalcouxThu, 06 Jun 2019 15:51:24 -0500https://ask.sagemath.org/question/46839/How to use a GPU for HPC?https://ask.sagemath.org/question/46754/how-to-use-a-gpu-for-hpc/From a sage code parallelized with map_reduce, what should be done for the computation to use a GPU (for high performance computing)?Sébastien PalcouxFri, 31 May 2019 21:43:25 -0500https://ask.sagemath.org/question/46754/Is map_reduce working for parallel computing? How?https://ask.sagemath.org/question/46711/is-map_reduce-working-for-parallel-computing-how/The following computation was done on a computer with 16 CPUs.
![image description](/upfiles/15592161891060146.png)
sage: seeds = [[]]
....: succ = lambda l: [l+[0], l+[1]] if len(l) <= 22 else []
....: S = RecursivelyEnumeratedSet(seeds, succ,structure='forest', enumeration='depth')
....: map_function = lambda x: 1
....: reduce_function = lambda x,y: x+y
....: reduce_init = 0
....: %time S.map_reduce(map_function, reduce_function, reduce_init)
....:
CPU times: user 15 ms, sys: 47 ms, total: 62 ms
Wall time: 58.4 s
16777215
But it seems that the computation did not exploit the CPUs in parallel, as the following screenshot show.
**Question**: What's wrong? How to exploit the CPUs in parallel?
![image description](/upfiles/15592157095194797.png)Sébastien PalcouxThu, 30 May 2019 06:39:40 -0500https://ask.sagemath.org/question/46711/How to implement a parallelization?https://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/Consider a code of the kind *tree exploration amassing fruits*: when the procedure arrives to a new node of the tree, if it is a leaf a possible fruit is collected, else a computation is done to determine the children of the node. I would like to parallelize as follows: the children are allocated to all the available CPUs, each CPU has a queue and a given child is allocated to the CPU with the smallest queue.
It seems to be a generic way to parallelize such a tree exploration.
**Question**: How to implement such a parallelization?
In addition, how to use GPU (for HPC)?
The code has the following form:
cpdef function(list L1, list L2):
cdef int i,n #...
cdef list LL1,LL2 #...
#...
# core of the code
#...
n= #...
for i in range(n):
LL1= #...
LL2= #...
function(LL1,LL2)Sébastien PalcouxMon, 27 May 2019 00:14:24 -0500https://ask.sagemath.org/question/46682/Fast numerical computation of eigenvalueshttps://ask.sagemath.org/question/44531/fast-numerical-computation-of-eigenvalues/I am trying to calculate the eigenvalues of a large (say, n=1000 to 10000) sparse Hermitian square matrix using SAGE
> numpy.linalg.eigvalsh(MyMatrix)
takes very long. I noticed it utilizes only a single core of my CPU.
How would one go about speeding the calculation? Specifically, I'm looking for a solution using parallel computation, or maybe something which is "more compiled".
Thank you.SageMathematicianSat, 01 Dec 2018 12:10:10 -0600https://ask.sagemath.org/question/44531/