ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 30 May 2020 07:51:15 +0200Are there fast(er) ways to compute inverses of Hermitian matrices?https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/I'm dealing with some Hermitian matrices valued in symbolic expressions. I need to be able to compute inverses of these matrices, but they seem to get big pretty fast. That is it would nice to be able to do this in a reasonable amount of time with 10x10 matrices at least, and hopefully larger than that.
I'm currently running a cell where the inverses of 2 10x10 matrices are being computed, and it's taken well over 10 minutes.
Are there ways to exploit the fact that these matrices are Hermitian to compute the inverses faster, and/or are there better ways to compute inverses of symbolic matrices than the standard .inverse()??
EDIT: I originally avoided an example, because their construction is somewhat convoluted as you'll see below.
First we have two variables which for which I want to run the larger program for various choices thereof.
p = 1, q= 5
X = {(i): var("X_{}".format(i), latex_name="X_{}") for i in range(2*p*q)}
e = {(i,j,k): var("e_{}{}{}".format(i,j,k), latex_name="e_{{{}{}{}}}".format(i,j,k)) for i in range(2) for j in range(q) for k in range((p+q))}
The following creates a list L such that L[i] is the collection of lists of length i whose elements are integers between 0 and q-1 in strictly increasing order. This is used throughout the larger program.
L = [[[]]]
LL = []
for i in range(q):
LL.append([i])
L.append(LL)
if q>=2:
for k in range(2,q+1):
LLL = []
for i in range(binomial(q, k-1)):
for j in range(q):
if L[k-1][i][len(L[k-1][i])-1]<j:
mm = []
for t in L[k-1][i]:
mm.append(t)
mm.append(j)
LLL.append(mm)
L.append(LLL)
Here, a matrix is defined which we be used to construct the matrices I'm interested in.
HE = matrix(SR, q, q)
for i in range(q):
for j in range(q):
prod = 0
for k in range(p):
prod -= (e[(0, i, k)]*e[(1, j, k)])
for l in range(p+q):
if l>=p:
prod += (e[(0, i, l)]*e[(0, j, l)])
HE[i,j] = prod
h = {(i): var("h_{}".format(i)) for i in range(q+1)}
for i in range(q+1):
h[i] = matrix(SR, binomial(q, i), binomial(q, i))
h[0][0,0] = 1
for i in range(1, q+1):
for z in L[i]:
for w in L[i]:
h[i][L[i].index(z), L[i].index(w)] = HE[z, w].det()
Finally, we come to the inverse matrices I would like to compute. It is absolutely necessary that I have these inverse matrices.
hinv = {(i): var("hinv_{}".format(i)) for i in range(q+1)}
for i in range(q+1):
hinv[i] = h[i].inverse()sum8tionSat, 30 May 2020 07:51:15 +0200https://ask.sagemath.org/question/51638/Does anyone know how to implement a simple XL Algorithm in sage?https://ask.sagemath.org/question/41818/does-anyone-know-how-to-implement-a-simple-xl-algorithm-in-sage/I need to implement the XL algorithm in sage, which i can use to solve over-determined systems of polynomial equations (more equations than variables). Any help on how to do this?
DalvirThu, 29 Mar 2018 14:45:45 +0200https://ask.sagemath.org/question/41818/Recursive Algorithm for Graph Coloringhttps://ask.sagemath.org/question/34051/recursive-algorithm-for-graph-coloring/In a 2014 article by Exoo, Ismailescu, and Lim ("On the Chromatic Number of R^4"), a recursive algorithm is described that verifies the absence of a proper $k$-coloring of a graph $G$. The authors include only the following description of the algorithm.
"[The program is] based on the following recursive procedure that does an exhaustive search for a $K$-coloring of a graph of order $N$. It employs a global variable *color*, an array of order $N$, which records the color of each vertex $v$ for $1 \leq v \leq N$. The search is initiated with the call DFS(1)."
procedure DFS(v):
Local variable: FCSet - the set of feasible colors for vertex v.
if v > N:
All vertices have been colored, report G is K-colorable.
Exit.
end if
FCSet = {1 ... K}
for u = 1 to v-1:
if u is adjacent to v:
FCSet = FCSet - color(u)
end if
end for
for c in FCSet:
color(v) = c
DFS(v+1)
end for
end procedure
I am having difficulty implementing this algorithm in Sage. Given the nature of the program, I thought Java would be a more natural programming language to use for this algorithm, but I'm afraid I am not familiar with Java syntax.
Any help with implementing this algorithm would be greatly appreciated! JEAThu, 07 Jul 2016 19:53:25 +0200https://ask.sagemath.org/question/34051/Finding all shortest paths between given (specific) pair of verticeshttps://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/I am working with graphs in sage and need a method of finding all shortest paths between some pair (or all pairs) of vertices.
Note that it is important to have all shortest paths registred, not just one, as seen in many Bellman-Ford/Dijkstra implementations (for instance Graph.shortest_path_all_pairs or networkx.algorithms.shortest_paths.all_pairs_shortest_path), and not just a number of those paths.
I am also satisfied with only a list of "optimal" predecessors... as long as the list is complete.
Thank you for answers!MorgothTue, 09 Jul 2013 07:45:53 +0200https://ask.sagemath.org/question/10332/optimizing graph coloring for small chromatic numberhttps://ask.sagemath.org/question/25395/optimizing-graph-coloring-for-small-chromatic-number/I am using Sage to compute chromatic number of some moderately large graphs G (a few thousand vertices). These graphs are relatively sparse (average degree < 15) and the chromatic number is fairly small–––the graphs I've been looking at tend to have chromatic number either 4 or 5. For my purposes, though, there is a big difference between 4 and 5.
––I've been using G.chromatic_number() as a black box, but is there some way I could just ask Sage directly if the graph is 4-colorable? (If the answer is 'no' maybe I don't care about whether the chromatic number is actually 5, 6, or larger.)
––Also, is there anything else I can do to optimize chromatic number calculations in Sage if I know a priori that the chromatic number is relatively small?
MattKahleSun, 04 Jan 2015 21:35:41 +0100https://ask.sagemath.org/question/25395/Silverman Appendix Ghttps://ask.sagemath.org/question/11140/silverman-appendix-g/Hi, I would like to know if there are any functions/plans that put in practice the algorithms from Appendix G of [Silverman's "The Xedni Calculus and the ECDLP"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.7851).BlackadderThu, 17 Apr 2014 00:15:36 +0200https://ask.sagemath.org/question/11140/Matlab flight simulator display indicator queryhttps://ask.sagemath.org/question/8878/matlab-flight-simulator-display-indicator-query/Hello
I'm working on a flight simulator at the moment within Matlab. I've hooked it up to a joystick and i have great control of yaw, roll, pitch, VTOL, thrust reversers and more! One nice little feature I have made in an m-file is an altitude and speed indicator. These indicators are basically two plots of an outer circle and inner circle and then a dial inside pointing to a value.
The idea is as the aircraft flies, the dial changes indicating speed.
However, I can't quite figure out how to implement this in real time within simulink. I can't use X-Y plots as I require more than one plot on the figure. The needle needs to move simultaneously (or at least with as little delay as possible) with the simulation.
Any help would be greatly appreciated!!!
Justraja13Wed, 11 Apr 2012 23:58:35 +0200https://ask.sagemath.org/question/8878/list of algorithms not implemented in Sage for contributorshttps://ask.sagemath.org/question/8656/list-of-algorithms-not-implemented-in-sage-for-contributors/Hello all!
I would like to know if there is some list of algorithms that are not implemented in Sage and that are important (for ex. because of its speed).
I think that it would be great for contributors. I believe the greatest things are mostly free and that Sage is very good example of this. Lot of algorithms in Sage are the fastest (when I compare it with 'ma' softwares) and that is really amazing that something free and open source for everyone can do it! For this reason I would like to contribute to this project and think that the list of important algorithms that arent still implemented in Sage would be great 'to do list' for contributors.
Thanks,
MartinMartin MaxaSun, 22 Jan 2012 08:22:06 +0100https://ask.sagemath.org/question/8656/How do I find if/where a specific algorithm has been implementedhttps://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/Hi
Since beginning using Sage, I have often been in the position that I need to find a specific algorithm for solving some problem. I might or might not already know that Sage has _some_ algorithm for doing it, but I want this one (for some reason). Is there an index or an easy way to search for this? The times I have tried using the search bar of sagemath.org, it has mostly been irrelevant posts, while a search on google like "<algorithm-name> site:sagemath.org" can give a bit as it also searches through the comments of the source code; but this is not very user-friendly, and it can take some time from finding some comment in a file, to know how to actually invoke specifically that code.
An example of this is the Berlekamp-Zassenhaus algorithm for factorising polynomials over integers.jsrnThu, 19 Aug 2010 03:49:49 +0200https://ask.sagemath.org/question/7580/