$ as a $Q$-set because every element in $\$ has the form $ih + a$ for some $i < n$ and $a \in Q$. In terms of algebras, $\kk[Q,h] = \kk[Q][x_h]/$relations, and all the relations will have the form $\xx^a x_h = \xx^b$, where $a,b \in Q$ and $a+h = b$ (proof: the relations obviously hold in $\kk[Q,h]$, and the induced map $\kk[Q][x_h]/$relations $\to \kk[Q,h]$ of $\kk[Q]$-modules is an isomorphism of vector spaces). If worse comes to worst, do the following now: each Hilbert basis element $h$ of $Q^\sat$ satisfies $n_h h \in Q$ for some $n_h \in \NN$ (easy to calculate: look for relation of the form $x_h^{n_h} - \xx^{\rm other\ stuff}$ in the toric ideal for $\$ using any term order in which $h$ is really heavy, so that $x_h^{n_h}$ is in the initial ideal, or in which $\xx^{\rm other\ stuff}$ is so light, that it will never get chosen). The set of all monomials $\prod_h x_h^{i_h}$ in which $i_h < n_h$ for each~$h$ generate $\kk[Q^\sat]$ as a $\kk[Q]$-module. The only remaining question is how to get the relations satisfied by these monomials. Start by choosing a subset of the monomials $m$ in the $x_h$ variables in such a way that each monomial maps to a different element in $\kk[Q^\sat]$. Take the direct sum of $\kk[Q]$-modules $\kk[Q,m]$ over all these monomials~$m$. Mod out this direct sum by a couple of things. First, kill all diagonals---that is, identify all of the copies of $\kk[Q]$ inside these $\kk[Q,m]$. The result has $\kk$-vector space dimension~$1$ in all $Q$-graded degrees. Now find the toric ideal for $Q^\sat$ using variables $x_h$ for Hilbert basis elements of $Q^\sat$ and other variables for~$Q$. Mod out by all relations in this toric ideal that happen to lie in the degrees of the monomials~$m$, treating any product of the $x_h$ variables as the (now unique, because of the first sentence in this paragraph) monomial the multiply to. That is, we get relations of the form $\xx^a m = \xx^b m'$ whenever $a + \deg(m) = b + \deg(m')$ in $Q^\sat$ and $a,b \in Q$. The resulting quotient has vector space dimension~$1$ in every $Q^\sat$-graded degree, by construction. Since these relations all obviously hold in $\kk[Q^\sat]$, there is a natural induced map from the resulting quotient to $\kk[Q^\sat]$, and we have just seen that the map is an isomorphism. Note that, once we know {\em any} $\kk[Q^\sat]$-module $M$ as a $\kk[Q]$-module, we know how to express every $\kk[Q^\sat]$-submodule $M' \subseteq M$ as a $\kk[Q]$-module. Indeed, it suffices to give a generating set for $M'$. But this is easy: take the generating set for $M'$ as a $\kk[Q^\sat]$-module (assume this has been given), and then simply multiply these by the generators of $\kk[Q^\sat]$ as a $\kk[Q]$-module. This multiplication takes place over $\kk[Q^\sat]$, but the elements thus produced can be just as easily considered over $\kk[Q]$. This is how we make any $\kk[Q^\sat]$-ideal of $\kk[Q^\sat]$ into a module over $\kk[Q]$. % }\end{excise}% % %end{section}{Computing with irreducible hulls}%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Computing injective resolutions}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{sec:injres} In this section the semigroup~$Q$ is not required to be saturated. Our goal is the main result (Theorem~\ref{t:injres}) in the first half of the paper: an algorithm to compute injective resolutions of finitely generated modules over~$\kk[Q]$, in the $\ZZ^d$-graded setting. That is, given generators and relations for a finitely generated $\ZZ^d$-graded module~$M$, we will compute an exact sequence $0 \to M \to J^0 \to J^1 \to \cdots$\ in which $J^i$ is a $\ZZ^d$-graded injective module for each~$i$. Of course, we shall only say how to calculate up to some specified cohomological degree, as injective resolutions usually do not terminate. This will not pose a problem for our subsequent computation in Section~\ref{sec:injalg} of local cohomology, which % always vanishes past cohomological degree~\mbox{$d+1$} anyway. The upshot is to reduce the computation of injective resolutions to finding irreducible hulls of finitely generated $Q$-graded modules and computing their cokernels, which we have already done in Section~\ref{sec:irred}. The data structures we employ for $\ZZ^d$-graded injective resolutions are the matrices we introduce in the next definition. \begin{defn}\rm \label{d:injmat} A \bem{monomial matrix} is a matrix of constants~$\lambda_{qp}$ along with \begin{numbered} \item a vector~$\alpha_q \in \ZZ^d$ and a face~$F_q \in Q$ for each row, and \item a vector~$\alpha_p \in \ZZ^d$ and a face~$F_p \in Q$ for each column \end{numbered} % \item such that $\lambda_{qp} = 0$ unless $F_p \subseteq F_q$ and $\alpha_p \in \alpha_q + F_q-Q$. % %endn{umbered} \end{defn} These monomial matrices generalize those in \cite{Mil2}, which were for $Q = \NN^d$. To any monomial matrix we can associate a map $J \mapsto J'$ of injective modules in the following manner. Each row and column label gives the data of an indecomposable injective; we think of the row labels as giving summands of~$J$ and the column labels as giving summands of~$J'$. To give a map from~$J$ to~$J'$ is thus the same as giving a matrix of maps from the row indecomposables to the column indecomposables. Such a map $\kk\{\alpha_q + F_q-Q\} \mapsto \kk\{\alpha_p + F_p-Q\}$ is necessarily zero unless $F_p \subseteq F_q$ and $\alpha_p \in \alpha_q + F_q-Q$. In the latter case it is determined by a single scalar~$\lambda_{qp}$. Hence $$ \begin{array}{@{\ }c@{\ \;}c@{\ \;}c@{\ \;}} & \injmatrix {\vdots & \vdots\:\\F_q & \alpha_{q\!}\\\vdots & \vdots\:\\} {\begin{array}{c} \cdots\ F_p\ \cdots\\ \cdots\ \alpha_p\ \cdots\\[.5ex] \\ \lambda_{qp} \\ \\ \end{array}} {\\\\\\} \end{array} $$ is a monomial matrix representing a map $$ \bigoplus_q \kk\{\alpha_q + F_q-Q\}\ \mapsto\ \bigoplus_p \kk\{\alpha_p + F_p-Q\}. $$ The component $\kk\{\alpha_q + F_q-Q\} \mapsto \kk\{\alpha_p + F_p-Q\}$ of this homomorphism takes $\xx^\alpha$ to $\lambda_{qp}\xx^\alpha$ for all $\alpha \in \alpha_p + F_p-Q$, and is zero elsewhere. Note that in degree $\alpha$, the map $J_{\alpha} \mapsto J'_{\alpha}$ given by a monomial matrix is obtained by deleting the rows and columns labeled by $\alpha_p, F_p$ such that $\alpha$ does not lie in $\alpha_p + F_p-Q$. (This corresponds to ignoring those summands of $J$ and $J'$ not supported at $\alpha$.) Ignoring the labels on what remains gives us a matrix with entries in $\kk$, which defines the $\kk$-vector space map $J_{\alpha} \mapsto J'_{\alpha}$. Two monomial matrices represent the same map of injectives (with given decompositions into direct sums of indecomposable injectives) if and only if (i)~their scalar entries are equal, (ii)~the corresponding faces~$F_r$ are equal, where $r = p,q$, and (iii)~the corresponding vectors~$\alpha_r$ are congruent modulo~$\ZZ F_r$. Rather than compute directly with cumbersome, infinitely generated injectives, it is more convenient to approximate injective resolutions using irreducible sums. % References for irreducible and injective resolutions are % \cite{MilIrr} and \cite[Chapter~11]{cca}. \begin{defn}\rm \label{d:irredres} An \bem{irreducible resolution} of a $Q$-graded module $M$ is an exact sequence $0 \to M \to \WW^0 \to \WW^1 \to \cdots\ $ in which each $\WW^j$ is an irreducible sum. \end{defn} Irreducible resolutions are approximations to injective resolutions; indeed, the $Q$-graded part of any injective resolution is an irreducible resolution \cite[Theorem~2.4]{MilIrr}. In particular, monomial matrices just as well represent homomorphisms of irreducible sums, as long as the degree labels $\alpha_q$ and~$\alpha_p$ all can be chosen to lie in~$Q$. The (apparent) advantage to irreducible resolutions over injective resolutions is their finiteness. \begin{cor} \label{c:irredres} For any finitely generated $Q$-graded $\kk[Q]$-module\/~$M$, Propositions~\ref{p:relations} and~\ref{p:irred} inductively compute a minimal irreducible resolution $\WW^\spot$ of\/~$M$ \mbox{algorithmically}. \end{cor} \begin{proof} Minimal irreducible resolutions have finite length (that is, they vanish in all sufficiently high cohomological degrees) by \cite[Theorem~2.4]{MilIrr}. The computability therefore follows from Propositions~\ref{p:relations} and~\ref{p:irred} by induction on the highest cohomological degree required. % Consider the set $V(M)$ of degrees $a \in Q$ such that $M_b$ % vanishes for all $b \in a+Q$. The vector space $\kk\{V(M)\}$ is % naturally an ideal in~$\kk[Q]$. It follows from % Algorithm~\ref{a:irred} that $V(M) \subset V(\WW/M)$ is a proper % subset whenever $\WW$ is an irreducible hull of~$M$ and $M \neq 0$ % (that is, $V(M) \neq Q$). The noetherianity of $\kk[Q]$ plus this % strict containment force the sequence of ideals % $$ % \kk\{V(M)\}\ \subseteq\ \kk\{V(\WW^0/M)\}\ \subseteq\ % \kk\{V(\WW^1/{\rm image}(\WW^0))\}\ \subseteq\ \cdots % $$ % to stabilize at the unit ideal of~$\kk[Q]$ after finitely many % steps. \end{proof} % As we have seen in Theorem~\ref{t:decomp}, we need to know the % entire injective resolution of $M$ up to cohomological degree~$i+1$ % in order to calculate the local cohomology $H^i_I(M)$ by applying % $\GI$ and taking cohomology. % comment{make this sentence more % ``algorithmic''} The next result demonstrates the precise manner in which irreducible resolutions approximate injective resolutions for computational purposes. \begin{prop} \label{p:Qgraded} Let $M$ be a finitely generated module with minimal injective resolution $J^\spot$ and minimal irreducible resolution $\WW^\spot$. Suppose that every indecomposable summand in the first $n$ cohomological degrees of $J^\spot$ has nonzero $Q$-graded part. Then $M$ is $Q$-graded, and the data contained in the first $n$ stages of $\WW^\spot$ constitute a finite data structure for the first $n$ cohomological degrees of~$J^\spot$. \end{prop} \begin{proof} Every map in $J^\spot$ can be expressed using the finite data of a monomial matrix, and this data can be read immediately off the maps in~$\WW^\spot$. \end{proof} If we can algorithmically determine a $\ZZ^d$-graded shift of $M$ so that the hypotheses of Proposition~\ref{p:Qgraded} are satisfied, then we can compute the minimal injective resolution of~$M$ up to cohomological degree~$n$. This task requires a lemma, in which $\mm$ denotes the maximal ideal $P_{\{\0\}}$ generated by nonunit monomials in~$\kk[Q]$. \begin{lemma} \label{l:pinnacle} Let $J^\spot$ be a minimal injective resolution of a finitely generated module $M$, and $F$ a face of\/~$Q$. If every indecomposable summand of\/ $\Gm J^{j+d-\dim(F)}$ has nonzero $Q$-graded part, then every indecomposable summand of~$J^j$ isomorphic to a $\ZZ^d$-graded shift of\/ $\kk\{F-Q\}$ has nonzero $Q$-graded part. \end{lemma} \begin{proof} \cite[Proposition~3.5]{HelM}, in the special case of an affine semigroup ring. \end{proof} Every indecomposable summand of $\Gm J^j$ is a shift $\kk\{\alpha-Q\}$ of~$\kk\{-Q\}$. Such an indecomposable injective has nonzero $Q$-graded part if and only if $\alpha \in Q$. % its \bem{socle}---that is, Our final lemma in this section describes the (standard) way to calculate the shifts $\alpha$ appearing in $\Gm J^j$. The number $\mu^{j,\alpha}(M)$ of shifts $\kk\{\alpha-Q\}$ appearing as summands in cohomological degree $j$ of the minimal injective resolution of~$M$ is called the $j^\th$ \bem{Bass number} of~$M$ in degree $\alpha$. \begin{lemma} \label{l:bass} Let $\FF_\spot$ be a free resolution of the residue field~$\kk$. The Bass number $\mu^{j,\alpha}(M)$ is effectively computable as the $\kk$-vector space dimension of $H^j(\FF_\spot, M)_\alpha$. \end{lemma} \begin{proof} This expression of Bass numbers as dimensions (over $\kk$) of Ext modules is standard; see \cite[Chapter~3]{BH}. The computability follows because we can calculate free resolutions, homomorphisms, and homology over~$\kk[Q]$. \end{proof} Now we come to our central result. For notation, $M(-a)$ denotes the $\ZZ^d$-graded shift of~$M$ up by~$a$, so that $M(-a)_b = M_{b-a}$. \begin{thm} \label{t:injres} Fix a finitely generated $\kk[Q]$-module $M$ and an integer~$i$. There is an algorithmically computable $a \in Q$ for which % $M(-a)$ satisfies the hypotheses of Proposition~\ref{p:Qgraded}. Propositions~\ref{p:relations} and~\ref{p:irred} inductively compute % the minimal irreducible resolution of $M(-a)$, and therefore it % effectively computes the minimal injective resolution of~$M(-a)$ through cohomological degree~$i+1$. \end{thm} \begin{proof} After using Lemma~\ref{l:bass} to compute the Bass numbers of $M$ up to % and including cohomological degree $i+1+\dim(M)$, choose $a$ so that the corresponding Bass numbers of $M(-a)$ have $\ZZ^d$-graded degrees lying in~$Q$. At this point, $M(-a)$ satisfies the hypotheses of Proposition~\ref{p:Qgraded} with $n=i+1$, by Lemma~\ref{l:pinnacle}. Now apply Corollary~\ref{c:irredres}. \end{proof} %end{section}{Computing injective resolutions}%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Sector partitions from injectives}%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{sec:decomp} % comment{requires $Q$ saturated, but only because of the % polyhedrality condition on sectors} We turn now to sector partitions, for which we assume henceforth that the affine semigroup $Q$ is saturated. As a prerequisite to producing sector partitions of local cohomology modules, we demonstrate in this section that injective modules admit sector partitions, as does the homology of any complex of injective modules. \begin{prop} \label{p:sectors} % Theorem~\ref{t:decomp} holds for $M$ injective. Suppose~$J = \bigoplus_{i=1}^r J_i$ is an injective module decomposed into summands \mbox{$J_i = \kk\{\alpha_i + F_i-Q\}$}. For each subset $A \subseteq \{1, \dots, r\}$ define~$S_{\!A}$ to be the set \begin{eqnarray*} S_{\!A} &=& \{\alpha \in \ZZ^d \mid (J_i)_\alpha \cong \kk \hbox{ for } i \in A\} \end{eqnarray*} of all degrees in\/~$\ZZ^d$ such that the summands of~$J$ nonzero in that degree are precisely those indexed by~$A$. % If we discard those~$A$ for which $S_{\!A}$ is empty, the remaining The sets~$S_{\!A}$ canonically determine a sector partition $\SS(J) \vdash J$. \end{prop} \begin{proof} For each $\alpha \in \ZZ^d$, either $(J_i)_\alpha = \{0\}$ or $(J_i)_\alpha = \kk\cdot\xx^{\alpha}$. Therefore $\SS(J)$ is indeed a partition of~$\ZZ^d$. Now we must show that $S_{\!A}$ is a finite union of polyhedra as in part~1 of Definition~\ref{d:sector}. The set $\alpha + F-Q$ of degrees is the set of lattice points in a polyhedron of the desired form because the half-spaces whose intersection is $\alpha + F-Q$ are bounded by hyperplanes parallel to facets of~$Q$, by definition. These hyperplanes divide~$\ZZ^d$ into finitely many disjoint regions (place the lattice points lying on each hyperplane in the region on the positive side of that hyperplane), each of which consists of the lattice points in a polyhedron of the desired form. Thus the complement $\ZZ^d \minus (\alpha + F-Q)$ is the required kind of finite union. We conclude that $S_{\!A}$ is a finite union of regions, each of which is an intersection of $r$ polyhedral regions---one from each of the summands~$J_i$. For each index set~$A$ such that $S_{\!A}$ is nonempty, define $J_{S_{\!A}} \subseteq \kk^r$ to be the subspace spanned by the basis vectors~$e_i$ such that $i \in A$. Then for each degree~$\alpha$ in~$S_{\!A}$, the map $J_\alpha \to J_{S_{\!A}}$ required by part~2 of Definition~\ref{d:sector} can be taken to equal the zero map on $(J_i)_\alpha$ for $i$ not in~$A$, and the map sending $\xx^\alpha$ to~$e_i$ on $(J_i)_\alpha$ for $i$ in~$A$. To define the maps $\xx^{S_B - S_{\!A}}$ for index sets $A$ and~$B$ such that $S_B - S_{\!A}$ is nonempty, as in part~3 of Definition~\ref{d:sector}, it suffices to define the image of~$e_i$ for each~$i$ in~$A$. We take $\xx^{S_B - S_{\!A}}(e_i) = e_i$ if $i$ is in~$B$, and $\xx^{S_B - S_{\!A}}(e_i) = 0$ otherwise. Commutativity of the required diagram follows from the definition of the module structure on $\kk\{\alpha_i + F_i-Q\}$. Specifically, for $\alpha \in S_{\!A}$ and $\beta \in S_B$ with $\beta - \alpha \in Q$, multiplication by $\xx^{\beta - \alpha}$ takes $\xx^{\alpha}$ to $\xx^{\beta}$ in $J_i$ for $i \in B$, and takes $\xx^{\alpha}$ to zero in $J_i$ for $i$ outside~$B$. \end{proof} The sector partition in Proposition~\ref{p:sectors} descends to the cohomology~$H$ of any complex of injectives, via monomial matrices. The forthcoming sector partition % $\SS(J^\spot) \vdash H$ of~$H$ is really determined {\em canonically}\/ by~$J^\spot$ (without its direct sum decomposition), even though the way we present things here makes it look like bases must be chosen. We chose this route because bases are good for computation, while uniqueness is immaterial. \begin{thm} \label{t:decomp} If $H$ is a module that can be expressed as the (middle) homology of a complex $J^\spot: J' \to J \to J''$ in which all three modules are injective, or all three modules are flat, then there is a % canonical sector partition $\SS(J^\spot) \vdash H$ determined % canonically by~$J^\spot$. \end{thm} % Algorithms for computating the sector partitions constructed here % appear in Section~\ref{sec:secposet}. \begin{proof} Choose direct sum decompositions to write $$ \begin{array}{r@{\ }c@{\ }l@{\quad\ }r@{\ }c@{\ }lcr@{\ }c@{\ }l} J' &=& \dis\bigoplus_{i=1}^{r'} J'_i, & J &=& \dis\bigoplus_{i=1}^r J_i, &\hbox{and}& J''\!&=& \dis\bigoplus_{i=1}^{r''} J''_i. \end{array} $$ Let $\Phi$ and $\Psi$ be the monomial matrices representing the maps $J' \mapsto J$ and $J \mapsto J''$, respectively. The sectors in the sector partition $\SS(J' \oplus J \oplus J'') \vdash J' \oplus J \oplus J''$ are indexed by triples $(A',A,A'')$ of subsets of $\{1,\ldots,r'\}, \{1,\ldots,r\}, \{1,\dots,r''\}$, respectively, and automatically satisfy the polyhedrality condition in part~1 of Definition~\ref{d:sector} by Proposition~\ref{p:sectors}. % The sector $S_{(A',A,A'')}$ equals the set of degrees~$\alpha$ such % that: % \begin{romanlist} % \item $J'_i$ is nonzero in degree $\alpha$ iff $i \in A'$, % \item $J_i$ is nonzero in degree $\alpha$ iff $i \in A$, and % \item $J''_i$ is nonzero in degree $\alpha$ iff $i \in A''$. % \end{romanlist} We take $\SS(J^\spot)$ to partition $\ZZ^d$ into these sectors. For each triple $(A',A,A'')$ we have maps $\Phi_{A'}^A: J'{}_{\!\!\!S_{\!A'}} \rightarrow J_{S_{\!A}}$ and $\Psi_{A}^{A''}: J_{S_{\!A}} \to J''{}_{\!\!\!\!S_{\!A''}}$ whose monomial matrices are defined by deleting: row~$i'$ of~$\Phi$ for $i'$ not in~$A'$; column~$i$ of~$\Phi$ and row~$i$ of~$\Psi$ for $i$ not in~$A$; and column~$i''$ of~$\Psi$ for $i''$ not in~$A''$. % (These matrices are with respect to the bases given in % Proposition~\ref{p:sectors}.) Let \begin{eqnarray} \label{eq:A} H_{S_{\!A',A,A''}} &=& \ker(\Psi_A^{A''})/\im(\Phi_{A'}^A). \end{eqnarray} For any $\alpha$ in $S_{\!A',A,A''}$, we have a commutative diagram \begin{equation} \label{eq:AA} \begin{array}{c@{\ }c@{\ }c@{\ }c@{\ }c} J'_{\alpha}&\longrightarrow&J_{\alpha}&\longrightarrow&J''_\alpha\\ \downarrow & &\downarrow& &\downarrow\\[-1.5ex] J'_{S_{A'}}&\stackrel{\Phi_{A'}^A}\too& J_{S_{\!A}} &\stackrel{\Psi_A^{A''}}\too&J''_{S_{A''}} \end{array} \end{equation} that induces the required isomorphism $H_\alpha \cong H_{S_{\!A',A,A''}}$. It is routine to check that the maps $H_{S_{\!A',A,A''}} \to H_{S_{B',B,B''}}$ induced from the corresponding maps on $J'_{A'}, J_A,$ and~$J''_{A''}$ commute with this isomorphism. \end{proof} % At this point, all that remains to prove Theorem~\ref{t:sector} is % to realize $H^i_I(M)$ in the form required by % Theorem~\ref{t:decomp}. Once we have Theorem~\ref{t:decomp}, the only step remaining to prove Theorem~\ref{t:sector} is to exhibit $H^i_I(M)$ as the homology of a complex of injectives. \begin{remark}\rm The results in this section hold just as well for \bem{flat} objects of~$\MM$, which are Matlis dual to injective objects and hence isomorphic to finite direct sums of modules of the form $\kk\{\alpha + F + Q\}$ for some $\alpha$ in~$\ZZ^d$ and some face~$F$ of~$Q$ \cite[Chapter~11]{cca}. % Although we have no use for flat modules in this paper, for the % record we state our general results here for flat as well as % injective $\ZZ^d$-graded modules. For the proofs, simply apply Matlis duality to the results for injectives. \end{remark} %end{section}{Sector partitions from injectives}%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Computing sector partitions}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{sec:secposet} % comment{again, requires $Q$ saturated, for the polyhedrality of % sectors} Again letting $Q$ be a saturated affine semigroup, the next task is actually computing the finitely many polyhedra whose lattice points comprise the sectors in the sector partition $\SS(J) \vdash J$ of an injective module. That is, we need to make % the first paragraph of the proof of Proposition~\ref{p:sectors} Proposition~\ref{p:sectors} and its proof into an algorithm. Since $Q$ is saturated, there are unique primitive integer linear functionals $\tau_1,\ldots,\tau_n$ taking $\ZZ^d \to \ZZ$, one for each facet of~$Q$, such that $Q = \bigcap_{i=1}^n \{\tau_i \geq 0\}$ is the set of lattice points in the intersection of their positive half-spaces. The degrees on which indecomposable injectives are supported can be expressed in terms of these linear functionals, via the following identity: \begin{eqnarray} \label{eq:cutout} \alpha + F-Q &=& \{\beta \in \ZZ^d \mid \tau_i(\beta) \leq \tau_i(\alpha) \hbox{ whenever } \tau_i(F) = 0\}. \end{eqnarray} In other words, $F-Q$ is the intersection of the {\em negative} half-spaces for those functionals~$\tau_i$ vanishing on~$F$, and $\alpha + F-Q$ is simply a translate. By convention, % $\tau_i \leq \infty$ on~$F-Q$ whenever $\tau_i$ fails to vanish % on~$F$. we use the notation $\tau_i(\beta) \leq \infty$ to mean that there is no restriction on the value of $\tau_i(\beta)$. This allows a notation $\tau_F(\alpha) \in (\ZZ\cup\infty)^n$ for the vector whose $i^\th$ coordinate satisfies \begin{eqnarray*} \tau_F(\alpha)_i &=& \left\{\begin{array}{@{}ll} \tau_i(\alpha) & \hbox{if }\tau_i(F) = 0\\ \infty & \hbox{otherwise.} \end{array}\right. \end{eqnarray*} The point is that a vector $\beta \in \ZZ^d$ lies in $\alpha + F-Q$ if and only if $\tau(\beta) \leq \tau_F(\alpha)$, where \begin{eqnarray*} \tau(\beta) &=& \big(\tau_1(\beta), \ldots, \tau_n(\beta)\big) \end{eqnarray*} and the `$\leq$' symbol denotes componentwise comparison. We shall use the corresponding definitions of $\tau_F(\alpha)$ and $\tau(\beta)$ for vectors $\alpha,\beta \in \RR^d = \RR \otimes \ZZ^d$, so $\tau_F(\alpha) \in (\RR\cup\infty)^n$. For the rest of this section, let \begin{eqnarray} \label{eq:J} J &=& \bigoplus_{j=1}^r J^j,\quad\hbox{with}\quad J^j\ =\ \kk\{\alpha_j + F_j-Q\}, \end{eqnarray} be an injective module, % While still in the saturated case $Q = Q^\sat$, and define \begin{eqnarray*} \tau^j &:=& \tau_{F_j}(\alpha_j) \quad\hbox{for } % i = 1,\ldots,n \hbox{ and } j = 1,\ldots,r. \end{eqnarray*} Thus for $i = 1,\ldots,n$ the vector $\tau^j$ has $i^\th$ coordinate $\tau^j_i = \tau_{F_j}(\alpha_j)_i$, which equals either $\tau_i(\alpha_j)$ or~$\infty$, depending on whether $\tau_i$ vanishes on~$F_j$ or not. Even without calculating the set~$\SS(J)$ algorithmically, the vectors~$\tau^j$ specify the map from~$\ZZ^d$ to~$\SS(J)$, by definition. We record a precise version of this statement in the next lemma. \begin{lemma} \label{l:store} A degree $\alpha \in \ZZ^d$ lies in $S_{\!A}$ if and only if \mbox{$A = \big\{j\!\in\!\{1,\ldots,r\} \mid \tau(\alpha) \leq \tau^j\big\}$}. \end{lemma} It remains to ascertain which sets~$S_{\!A}$ of lattice points are nonempty, and to determine the pairs $A,B$ for which we must compute a map $\xx^{B-A} : J_A \to J_B$. (The maps themselves, which are canonical, % given the direct sum decomposition of~$J$, are constructed in the proof of Proposition~\ref{p:sectors}.) For each functional~$\tau_i$ there is a permutation~$w_i$ of $\{1,\ldots,r\}$ satisfying $\tau_i^{w_i(1)} \leq \cdots \leq \tau_i^{w_i(r)}$. To simplify notation, we write $\tilde\tau_i^\ell$ instead of $\tau_i^{w_i(\ell)}$. Also, set $\tilde\tau_i^0 = -\infty$ and $\tilde\tau_i^{r+1} = \infty$. For fixed~$i$, the parallel affine hyperplanes $\{\tau_i = \tilde\tau_i^\ell\}_{\ell=1}^r$ divide $\ZZ^d$ into strips \begin{eqnarray*} \{\beta \in \ZZ^d \mid \tilde\tau_i^\ell + 1 \leq \tau_i(\beta) \leq \tilde\tau_i^{\ell+1}\} \end{eqnarray*} for $\ell = 0,\ldots,r$. At most $r+1$ of these strips are nonempty, because some of the hyperplanes may coincide. Also, the last few of the $\tilde\tau_i^\ell$ will equal~$\infty$; we interpret any strip where $\tau_i^\ell = \tau_i^{\ell+1} = \infty$ as empty, and ignore it. \begin{prop} \label{p:strips} Let $J$ be as in~(\ref{eq:J}). % and assume $Q = Q^\sat$ is saturated. For any fixed $\ell_1,\ldots,\ell_n \in \{0,\ldots,r\}$, the lattice points in the polyhedron \begin{eqnarray*} \Delta(\ell_1,\ldots,\ell_n) &:=& \bigcap_{i=1}^n\{\beta \in \RR^d \mid \tilde\tau_i^{\ell_i} + 1 \leq \tau_i(\beta) \leq \tilde\tau_i^{\ell_i+1}\} \end{eqnarray*} all lie inside a single sector in\/ $\SS(J)$. The partition of\/~$\ZZ^d$ by the polyhedra $\Delta(\ell_1,\ldots,\ell_n)$ refines the partition of\/~$\ZZ^d$ by the sectors in~$\SS(J)$. \end{prop} \begin{proof} This follows from the definitions and~(\ref{eq:cutout}), which uses that $Q$ is saturated. \end{proof} Proposition~\ref{p:strips} makes way for an algorithm to compute the set of sectors. \begin{alg}\rm \label{a:secset} \end{alg} \begin{alglist} \routine{input} $J = \bigoplus_{j=1}^r J^j$, an injective module over $\kk[Q]$, with $J^j = \kk\{\alpha_j + F_j-Q\}$ \routine{output} the set $\SS(J)$ of sectors, each expressed as a list of polyhedra that partition it \begin{routinelist}{define} \item[$\phi : \ZZ^d \to$] subsets of $\{1,\ldots,r\}$, as in Lemma~\ref{l:store} \end{routinelist} \begin{routinelist}{initialize} \item[$\AA := \{\}$,] the empty collection of subsets of $\{1,\ldots,r\}$ \end{routinelist} \routine{while} $\ell_1,\ldots,\ell_n \in \{0,\ldots,r\}$ \procedure{do} \begin{algsublist} \routine{if} $\Delta(\ell_1,\ldots,\ell_n)\neq\nothing$ \begin{algsublist} \routine{then} \procedure{define} $A := \phi(\Delta(\ell_1,\ldots,\ell_n))$ \routine{else} \procedure{next} $(\ell_1,\ldots,\ell_n)$ \end{algsublist} \routine{end} \procedure{if-then-else} \routine{if} $A \in \AA$ \begin{algsublist} \begin{routinelist}{then} \routine{redefine} $S_{\!A} := S_{\!A} \cup \{\Delta(\ell_1,\ldots,\ell_n)\}$ \end{routinelist} \begin{routinelist}{else} \routine{initialize} $S_{\!A} := \{\Delta(\ell_1,\ldots,\ell_n)\}$ \routine{redefine} $\AA := \AA\cup\{A\}$ \end{routinelist} \end{algsublist} \routine{end} \procedure{if-then-else} \routine{next} $(\ell_1,\ldots,\ell_n)$ \end{algsublist} \routine{end} \procedure{while-do} \routine{output} $\{S_{\!A} \mid A \in \AA\}$ \end{alglist} \medskip \noindent Note that $\phi$ is constant on $\Delta(\ell_1,\ldots,\ell_n)$ by definition, and can easily be determined directly from the data $(\ell_1,\ldots,\ell_n)$. Next comes the determination of which maps $\xx^{B-A}$ need computing. In the coming algorithm, we write $\Delta(\ell_1,\ldots,\ell_n) \leq \Delta(\ell_1',\ldots,\ell_n')$ if $(\ell_1,\ldots,\ell_n) \leq (\ell_1',\ldots,\ell_n')$ as vectors in $(\ZZ\cup\infty)^n$. Such notation is justified because $\Delta(\ell_1,\ldots,\ell_n) \not\leq \Delta(\ell_1',\ldots,\ell_n')$ automatically implies that $\Delta(\ell_1',\ldots,\ell'_n) - \Delta(\ell_1,\ldots,\ell_n)$ fails to intersect~$Q$. \begin{alg}\rm \label{a:secposet} % Again assume $Q = Q^\sat$ is saturated, so that % Algorithm~\ref{a:secset} applies. \end{alg} \begin{alglist} \routine{input} sectors $S_{\!A}$ and $S_B$ in $\SS(J)$ from the output of Algorithm~\ref{a:secset} \routine{output} the truth value of: % $S_{\!A} \preceq S_B$, as per Definition~\ref{d:sector} ``there exist $\alpha \in S_{\!A}$ and $\beta \in S_B$ with $\beta-\alpha \in Q$'' \routine{initialize} $\mathit{val} := $ \procedure{false} \routine{while} $(\Delta_A,\Delta_B) \in S_{\!A} \times S_B$ \procedure{and} $\mathit{val} = $ \procedure{false}, \procedure{do} \begin{algsublist} \routine{if} $A \supseteq B$ \procedure{and} $\Delta_A \leq \Delta_B$ \begin{algsublist} \routine{then} \procedure{define} $\Delta_B - \Delta_A:=$ the Minkowski sum of $\Delta_B$ and $-\Delta_A$ \routine{else} \procedure{next} $(\Delta_A,\Delta_B)$ \end{algsublist} \routine{end} \procedure{if-then-else} \routine{if} $Q \cap (\Delta_B - \Delta_A) \neq \nothing$ \begin{algsublist} \routine{then} \procedure{redefine} $\mathit{val}:=$ \procedure{true} \routine{else} \procedure{next} $(\Delta_A,\Delta_B)$ \end{algsublist} \routine{end} \procedure{if-then-else} \end{algsublist} \routine{end} \procedure{while-do} \routine{output} $\mathit{val}$ \end{alglist} The proof of correctness for Algorithm~\ref{a:secposet} is straightforward from the definitions, except for the first \procedure{if-then-else} procedure, which relies on Lemma~\ref{l:poset}, below. Note the non-necessity in Algorithm~\ref{a:secposet} of actually finding a witness in $\Delta_B - \Delta_A$ for $S_{\!A} \preceq S_B$; as we have seen in (\ref{eq:A}) and~(\ref{eq:AA}) from the proof of Theorem~\ref{t:decomp}, the natural map on cohomology is induced by taking submatrices of the monomial matrix, regardless of where the witnesses lie. % ... $S_{\!A} \preceq S_{B}$ and $S_{B} \preceq S_{\!A}$ together % imply $A = B$, and this is an immediate consequence of the % following. \begin{lemma} \label{l:poset} If $\SS(J)$ is as in Proposition~\ref{p:sectors}, then $Q \cap (S_{B} - S_{\!A}) \neq \nothing$ implies $A \supseteq B$. \end{lemma} \begin{proof} If $a \in Q$ and $(J_i)_\alpha = 0$, then $(J_i)_{a+\alpha} = 0$, so the set of summands nonzero in degree $a+\alpha$ can only be smaller. % Use the fact that $\ZZ^d \minus F-Q$ is closed under addition by % elements of~$Q$. \end{proof} Unfortunately, Algorithm~\ref{a:secposet} is necessary, because \hbox{$\Delta_B - \Delta_A \neq \nothing$} need not always hold when $\Delta_A \leq \Delta_B$, as the example to come shortly demonstrates. It does seem, however, that the offending pairs of polytopes are usually ``small''. For instance, we know of no examples where the lattice points in either polytope affinely span~$\ZZ^d$. \begin{example}\rm Let $Q$ be the subsemigroup of $\NN^2$ generated by $(2,0)$, $(1,1)$, and $(0,2)$. Name the faces of $Q$ as $\0, X, Y, Q$, and set $E_F = F-Q$. Let \begin{eqnarray*} J &=& \kk\{(0,0)+E_\0\}\,\oplus\,\kk\{(0,1)+E_X\}\,\oplus\,\kk\{(0,0)+E_Y\}\\ & &\phantom{\kk\{(0,0)+E_\0\}}\oplus \kk\{(0,-1)+E_X\}\oplus \kk\{(-2,0)+E_Y\}, \end{eqnarray*} with the summands labeled in order as $J_1,\ldots,J_5$. Letting $X$ be facet number~$1$ and $Y$ be facet number~$2$, the arrays $\tau_i^j$ and $\tilde\tau_i^\ell$ look like \begin{rcgraph} \left(\begin{array}{@{\,}c@{\,}}\tau_1^j\\\tau_2^j\end{array}\right) \ =\ \left( \begin{array}{@{\;}ccccc@{\;}} 0 & 1 & \infty & -1 & \infty\\[.5ex] 0 & \infty & 0 & \infty & -2 \end{array} \right) \qquad\hbox{and}\qquad \left( \begin{array}{@{\,}c@{\,}}\tilde\tau_1^\ell\\[.5ex] \tilde\tau_2^\ell\end{array} \right) \ =\ \left( \begin{array}{@{\;}ccccccc@{\;}} -\infty & -1 & 0 & 1 & \infty & \infty & \infty\\[.5ex] -\infty & -2 & 0 & 0 & \infty & \infty & \infty \end{array} \right) \end{rcgraph} The sectors $S_{\{1,2,3\}}$ and $S_{\{2,3\}}$ contain one polytope each, and both of these polytopes contain exactly one lattice point. Specifically, identifying the sector, the polytope, and the lattice point, we have $$ S_{\{1,2,3\}} = \Delta(-1,-2) = (0,0) \qquad\hbox{and}\qquad S_{\{2,3\}} = \Delta(0,-2) = (-1,1). $$ Now $\Delta(-1,-2) \leq \Delta(0,-2)$, but subtracting the vector in~$S_{\{1,2,3\}}$ from the one in~$S_{\{2,3\}}$ yields $(-1,1)$, which does not lie in the semigroup~$Q$.% \end{example} \begin{remark}\rm \label{rk:holes} The notion of sector partition ought to have a refinement that takes into account the various kinds of failures of saturation for arbitrary affine semigroup. The resulting notion would produce sector partitions for the cohomology of complexes of injectives over nonnormal affine semigroup rings. The failures of saturation fall into two categories: the geometric kind, arising from polyhedral ``holes'' in the semigroup (as compared with its saturation), and the arithmetic kind, arising from finite-index sublattices generated by faces. Even in the case where arithmetic failure is absent, however, we do not know how to bound the sizes and shapes of the ``holes'' sufficiently to carry out an analysis such as the one producing the algorithms above. % This remains true even though the ``holes'' in an unsaturated % semigroup~$Q$ occur in disjoint unions of polyhedral subsets whose % facets are parallel to the facets of~$Q$. % % normalization $\kk[Q^\sat]$ is a finitely generated module % over~$\kk[Q]$, and hence so is $\kk[Q^\sat]/\kk[Q]$, which is % supported precisely on the ``holes'' of~$\kk[Q]$. \end{remark} %end{section}{Computing sector partitions}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Computing local cohomology with monomial support}%%%%%%%%%%%%%% \label{sec:injalg} Still assuming that $Q$ is sturated, we have now finally developed enough tools to prove the main theorem on local cohomology with monomial support, namely Theorem~\ref{t:sector} from the Introduction. \begin{proofof}{Theorem~\ref{t:sector}} Take $i = d$ in Theorem~\ref{t:injres}, and let $J^\spot(-a)$ be the minimal $\ZZ^d$-graded injective resolution computed there. Then $J^\spot$ is an algorithmically computed injective resolution of~$M$. By definition, $H^i_I(M)$ is the middle cohomology of the complex % $$ % \GI J^\spot:\ \ \GI J^{i-1}\ \too\ \GI J^i\ \too\ \GI J^{i+1} % $$ $\GI J^{i-1} \to \GI J^i \to \GI J^{i+1}$, where $\GI J^j$ is the direct sum of all indecomposable summands of $J^j$ whose unique associated prime contains~$I$. Having now expressed $H^i_I(M)$ as the cohomology of an effectively computed complex of injectives, Theorem~\ref{t:decomp} says that $H^i_I(M)$ has a sector partition. The set of sectors in part~1 of Definition~\ref{d:sector} is computed by Algorithm~\ref{a:secset}. The vector spaces in part~2 of Definition~\ref{d:sector} are specified in (\ref{eq:A}) from the proof of Theorem~\ref{t:decomp}, and naturally determine the maps in part~3 of Definition~\ref{d:sector}, given the computation in Algorithm~\ref{a:secposet}. \end{proofof} % Our algorithms allow the computation of any single degree---or % indeed the maps between any two degrees---before the computation of % the sector set $\SS$ in step~(i). % % The sector computation in the injective algorithm only uses % homological data for~$M$, combined with geometric data for~$I$: we % need only compute the Bass numbers of $M$ at primes in the zero set % of~$I$. %end{section}{Computing local cohomology with monomial support}%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %section{Complexity issues}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %label{sec:complexity} Now we turn to issues of complexity. There is little sense in completing a formal complexity analysis of all of the algorithms presented in this paper, as they involve Gr\"obner basis computation, which is doubly-exponential from a worst-case perspective. However, it is worth mentioning where the complexity in our algorithms comes from, up to a factor arising from the complexity of Gr\"obner basis computation, since Gr\"obner basis computations are often more efficient than expected. The purpose of what follows, therefore, is to assure the reader that our algorithms have not amplified the faux-doubly-exponential complexity of Gr\"obner bases with some ``honest'' exponential complexity. Let us assume that the dimension~$d$ is fixed, and analyze the complexity of computing all of the local cohomology of a finitely generated module~$M$ supported on a fixed monomial ideal~$I$ over a normal semigroup ring~$\kk[Q]$. This computation involves all of the algorithms in the paper except the one in Section~\ref{sub:unsatgenrel}. (The complexity of Algorithm~\ref{a:unsat} above and beyond Algorithm~\ref{a:irred} is only about as bad as that of $\kk[Q^\sat]/\kk[Q]$ as a $\kk[Q]$-module, anyway.) % Let $\mathsf{b}$ denote the sum of all Bass numbers of~$M$ up to % cohomological degree~$d+1$. In Algorithm~\ref{a:irred}, the only non-Gr\"obner contribution to the running time comes from the number of basis elements constructed (see Remark~\ref{r:avoid}.2, which can be used to ensure that we only check faces of~$Q$ giving rise to basis elements). This number is by definition a Bass number of~$M$. Thus, up to Gr\"obner basis computation, Algorithm~\ref{a:irred} is only as complex as its output. % and simpler output is impossible. Next we consider % the complexity of the algorithm in Proposition~\ref{p:saturated}. The algorithm works by taking the union (over a set of facets of~$Q$) of ideals output by Algorithm~\ref{a:polytopes}. The output presents the generators of each such ideal as the lattice points in a union of polytopes having the form $\bigl((a + \RR H) \cap \RR_+ D\bigr) + G$, where $D$ is a face of~$Q$. % , the vector $a \in Q$ is part of the input, and $H$ is a given % support hyperplane of~$Q$. as in the \procedure{while-do} % procedure. The computation of each such polytope is by standard techniques to intersect polyhedra and take Minkowski sums with the fixed zonotope~$G$. Hence, up to factors coming from the number of facets of~$Q$ and from standard procedures, we need only bound \begin{numbered} \item the number of polytopes output by Algorithm~\ref{a:polytopes}, and \item the number of lattice points in each such polytope. \end{numbered} The former is polynomial in the number of facets of~$Q$ by Remark~\ref{r:polytopes}.2. The latter is polynomial in the input vector $a \in Q$ by the piecewise polynomiality of the % Ehrhart lattice point enumeration function of $(a + \RR H) \cap \RR_+ D$ as a function of~$a$ \cite{McMullen77}, along with the fact that $G$ is fixed. Actually computing the set of lattice points in each polytope can be accomplished using the efficient algorithms of Barvinok and Woods \cite{BarWoods}. \begin{remark}\rm \label{r:BarWoods} We need to do Gr\"obner basis computations with the irreducible ideals~$W$ output by the algorithm in Proposition~\ref{p:saturated}. This means that, for our purposes, the {\em short rational generating functions}\/ output by the algorithms of \cite{BarWoods} do not suffice: we actually require the list of lattice point explicitly, to get a generating set of~$W$ as a list of monomials. Thus the short generating functions must be expanded. To reduce complexity, the short generating functions can be post-processed using the methods of \cite{BarWoods} to yield short generating functions for the {\em minimal}\/ generators of the ideals~$W$ in question. Then we can expand only these ``minimal'' short generating functions. \end{remark} The remaining contributions to the complexity of our local cohomology computation come from Algorithm~\ref{a:secset}, which computes the sets of polytopes whose disjoint unions constitute the sectors, and Algorithm~\ref{a:secposet}. The latter is quadratic in the output of Algorithm~\ref{a:secset}, times a factor coming from the Minkowski sum operations and the decision procedure for whether each such sum contains a lattice point after intersecting with~$Q$. Therefore it remains only to analyze Algorithm~\ref{a:secset}. \begin{prop} \label{p:complexity} The number of polyhedra arising in Algorithm~\ref{a:secset} is polynomial in the Bass numbers of~$M$ and the number of facets of~$Q$. \end{prop} \begin{proof} Each Bass number of~$M$ represents an indecomposable injective module whose bounding hyperplanes subdivide $\RR^d$ into a number of regions. Consider the subdivision of $\RR^d$ obtained by taking simultaneously all of the hyperplanes corresponding all of the Bass numbers of~$M$. The number of hyperplanes contributed by each Bass number is at most the number of facets of~$Q$, so the total number of hyperplanes is at most the number of facets of~$Q$ times the sum of the contributing Bass numbers. It is well known (and follows by induction on~$n$ and the dimension~$d$) that $n$ hyperplanes subdivide $\RR^d$ into a number of regions that is a polynomial in~$n$ of degree~$d$. % the number of sectors (in fact, the number of polyhedra comprising % sectors) is polynomial in both the number~$r$ of summands and the % number~$n$ of facets of~$Q$. It is only exponential in the % dimension~$d$ of~$Q$. The reason is that the number of regions into % which the $r \cdot n$ hyperplanes subdivide $\RR^d$ is polynomial % in~$r \cdot n$. This standard result is proved by induction on the % number~$h$ of hyperplanes and the dimension~$d$, as follows. The % intersection of the last hyperplane with the others is a subdivision % of the last hyperplane. Thus subdivision has polynomially many % regions, the polynomial being of degree~\mbox{$d-1$} % in~\mbox{$h-1$}. Adding in the last hyperplane therefore creates % $O(h^{d-1})$ new regions. If $p(h)$ is a function whose first % difference is a polynomial of degree $d-1$ in~$h$, then $p(h)$ is % polynomial of degree~$d$. \end{proof} This proof shows that the number of polyhedra is exponential in the dimension. Exponential growth as a function of dimension also occurs in the analysis before Remark~\ref{r:BarWoods}, where we apply \cite{McMullen77}. \begin{remark}\rm \label{r:BV} A large number of rational polyhedra arise in the course of computing local cohomology modules. When the identification of all the lattice points in these polyhedra is necessary, the complexity of this task should be drastically reduced by the fact that most of these polyhedra have facets parallel to those of~$Q$ itself. Results such as those in \cite{BVvectPartFctn} could be helpful along these lines.% % comment{I personally don't know the best way to accomplish this, but % it should be interesting, perhaps using \cite{BVvectPartFctn}.} \end{remark} %end{section}{Complexity issues}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgments} We wish to thank Gennady Lyubeznik, who motivated us to make our previously abstract methods algorithmic. Both authors were partially supported by the National Science Foundation. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \footnotesize%\addcontentsline{toc}{section}{References}%%%%%%%%%%%%%%%% \bigskip %\noindent\comment{the referenced chapter in [MS04] is complete} %\bibliographystyle{amsalpha}\bibliography{biblio}\end{document}%%%%%%%% \def\cprime{$'$} \providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace} \begin{thebibliography}{EMS00.}%{EMS00} % \bibitem[Bar94]{Bar94} % Alexander~I. Barvinok, \emph{A polynomial time algorithm for counting % integral points in polyhedra when the dimension is fixed}, % Math. Oper. Res. \textbf{19} (1994), no.~4, 769--779. \bibitem[BH93]{BH} Winfried Bruns and J{\"{u}}rgen Herzog, \emph{Cohen--{M}acaulay rings}, Cambridge Studies in Advanced Mathematics, vol.~39, Cambridge University Press, Cambridge, 1993. \bibitem[BV97]{BVvectPartFctn} Michel Brion and Mich{\`e}le Vergne, \emph{Residue formulae, vector partition functions and lattice points in rational polytopes}, J. Amer. Math. Soc. \textbf{10} (1997), no.~4, 797--833. \bibitem[BW02]{BarWoods} Alexander Barvinok and Kevin Woods, \emph{{Short rational generating functions for lattice point problems}}, J. Amer. Math. Soc., to appear. \textsf{arXiv:math.CO/0211146} % \bibitem[DHTY03]{DHTY} % J.\ A.\ De Loera, R.\ Hemmecke, J.\ Tauzer, and R.\ Yoshida, % \emph{Effective lattice point counting in rational convex % polytopes}, J. Symbolic Comput., to appear. \bibitem[Eis95]{Eis} David Eisenbud, \emph{Commutative algebra, with a view toward algebraic geometry}, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995, first printing. \bibitem[EMS00]{EMS} David Eisenbud, Mircea Musta{\c{t}}{\v{a}}, and Mike Stillman, \emph{Cohomology on toric varieties and local cohomology with monomial supports}, J. Symbolic Comput. \textbf{29} (2000), no.~4-5, 583--600. \bibitem[Har70]{HarCofinite} Robin Hartshorne, \emph{Affine duality and cofiniteness}, Invent. Math. \textbf{9} (1969/1970), 145--164. \bibitem[HM03]{HelM} David Helm and Ezra Miller, \emph{Bass numbers of semigroup-graded local cohomology}, Pacific J. Math. \textbf{209} (2003), no.~1, 41--66. \bibitem[HS93]{HuSh} Craig Huneke and Rodney Sharp, \emph{Bass numbers of local cohomology modules}, Trans. Amer. Math Soc. \textbf{339} (1993), 765--779. \bibitem[Lyu93]{Lyu1} Gennady Lyubeznik, \emph{Finiteness properties of local cohomology modules (an application of ${D}$-modules to commutative algebra)}, Invent. Math. \textbf{113} (1993), no.~1, 41--55. \bibitem[McM77]{McMullen77} P.~McMullen, \emph{Valuations and {E}uler-type relations on certain classes of convex polytopes}, Proc. London Math. Soc. (3) \textbf{35} (1977), no.~1, 113--135. \bibitem[Mil98]{Mil9812095} Ezra Miller, \emph{Alexander duality for monomial ideals and their resolutions}, \textsf{math.AG/9812095}, 1998. \bibitem[Mil00]{Mil2} Ezra Miller, \emph{The {Alexander} duality functors and local duality with monomial support}, J. Algebra \textbf{231} (2000), 180--234. \bibitem[Mil02]{MilIrr} Ezra Miller, \emph{Cohen--{M}acaulay quotients of normal semigroup rings via irreducible resolutions}, Math. Res. Lett. \textbf{9} (2002), no.~1, 117--128. \bibitem[MS03]{cca} Ezra Miller and Bernd Sturmfels, \emph{Combinatorial commutative algebra}, version of 30 July 2003 (currently available at \textsf{http:/$\!$/math.umn.edu/\~{}\hspace{-.2ex}ezra}), in progress. \bibitem[Mus00]{Mus1} Mircea Musta{\c{t}}{\v{a}}, \emph{Local cohomology at monomial ideals}, J. Symbolic Comput. \textbf{29} (2000), no.~4-5, 709--720. % \bibitem[Smi00]{ggsmith00} % Gregory~G. Smith, \emph{Computing global extension modules}, % J. Symbolic Comput. \textbf{29} (2000), no.~4--5, 729--746. \bibitem[Ter99]{TerLocalCoh} Naoki Terai, \emph{Local cohomology modules with respect to monomial ideals}, preprint, 1999. \bibitem[Vas98]{Vas} Wolmer~V. Vasconcelos, \emph{Computational methods inn commutative algebra and algebraic geometry}, Algorithms and Computation in Mathematics, vol.~2, Springer-Verlag, Berlin, 1998, With chapters by David Eisenbud, Daniel R. Grayson, J\"urgen Herzog and Michael Stillman. \bibitem[Wal99]{Wal} Uli Walther, \emph{Algorithmic computation of local cohomology modules and the cohomological dimension of algebraic varieties}, J. Pure Appl. Algebra \textbf{139} (1999), 303--321. \bibitem[Yan01]{YanPoset} Kohji Yanagawa, \emph{Sheaves on finite posets and modules over normal semigroup rings}, J. Pure Appl. Algebra \textbf{161} (2001), no.~3, 341--366. \bibitem[Yan02]{YanMonSup} Kohji Yanagawa, \emph{Squarefree modules and local cohomology modules at monomial ideals}, Local cohomology and its applications (Guanajuato, 1999), Lecture Notes in Pure and Appl. Math., vol. 226, Dekker, New York, 2002, pp.~207--231. \end{thebibliography} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%