Given a Heegaard diagram $(\Sigma, \alpha, \beta)$ we obtain a compact 3-manifold $M$ together with a handle decomposition where the $\alpha$ curves are the belt spheres of the 1-handles and the $\beta$ curves are the attaching spheres of the 2-handles. We can compute the homology of the resulting 3-manifold using this handle decomposition. After choosing orientations for the $\alpha$, $\beta$, and $\Sigma$ we have a map
$$
\partial: \bigoplus\_i \mathbb{Z} \beta\_i \to \bigoplus\_j \mathbb{Z} \alpha\_j
$$
where $\partial = [\langle\beta\_i , \alpha\_j\rangle\_\Sigma]\_{i,j}$ and $\langle-,-\rangle\_{\Sigma}$ is the intersection form on $\Sigma$. We then have $H\_1(M) = \text{coker}(\partial)$ and $H\_2(M) = \text{ker}(\partial)$.


My questions are: 


(1) Given a homology class $[L] \in H\_1(M)$, represented by some immersed link, how can I find a linear combination of the $\alpha\_j$ that represent it?


(2) Given a homology class $[S] \in H\_2(M)$ represented by some immersed surface, how can I find a linear combination of the $\beta\_i$ representing it? 


I should probably also ask the converses - namely given some linear combination of $\alpha\_j$ where is a link that represents the homology class that they correspond to (I imagine it is just the linear combination itself) and given a linear combination of the $\beta\_i$ where is a surface representing the homology class that they correspond to?



Representing homology classes in a Heegaard diagram
I'll back away from your initial description a bit and use a little more notation for the handlebodies. Let $H\_g$ be a genus $g$ handlebody, and $S\_g$ the boundary surface. The 3-manifold $M$ is given by the disjoint union with an equivalence relation


$$ M = H\_g \sqcup H\_g / \sim $$


where the equivalence relation is generated by a diffeomorphism of the boundary, call it $f$. We think of $S\_g = \partial H\_g$. 


The Meyer-Vietoris sequence for the above decomposition gives the short exact sequence


$$ 0 \to H\_2 M \to \mathbb Z^{2g} \to \mathbb Z^{2g} \to H\_1 M \to 0$$


The map in the middle is 


$$f\_\* : H\_1 S\_g \to H\_1 H\_g \oplus H\_1 H\_g$$


can be thought of as a block-matrix


$$\pmatrix{ I & 0 \cr A & B }$$


provided we give $H\_1 S\_g$ a basis of non-trivial curves in $H\_1 H\_g$ followed by the belt circles for $H\_g$. This means $H\_1 M$ is isomorphic to $coker(B)$ and $H\_2 M$ is isomorphic to $ker(B)$, where $B$ is the matrix that represents the belt circles of the first handlebody (under $f$) in the homology of the 2nd handlebody, i.e. it is essentially the matrix in your question. 


To compute the homology class of a curve, for example:


* Any curve in $M$ can be isotoped to live in just the 2nd handlebody. Once it's in the 2nd handlebody, you can read off its homology class by taking the intersection numbers with the belt discs (for the 2nd handlebody). The fact that you can perturb the curve to live in the 2nd handlebody comes from making it transverse (i.e. disjoint) to the "core" of the first handlebody, then using the fact that the first handlebody is the mapping cylinder from the boundary surface to the "core" (which is a graph, homotopy-equivalent to a wedge of $g$ circles).
* If the isotopy is too much work, you could compute the curves intersections with the belt discs in both handlebodies. That gives you a representative in $H\_1 H\_g \oplus H\_1 H\_g$ describing the class. This intersection argument comes from the Poincare duality isomorphism $H\_1 H\_g \simeq H^2(H\_g, S\_g) \simeq Hom(H\_2(H\_g, S\_g), \mathbb Z)$, and the fact that $H\_2(H\_g, S\_g)$ is generated by the belt discs.


For $H\_2 M$, it's similar. Meyer-Vietoris tells you to cut your surface into the regions in the 1st handlebody, and take its boundary. That's the map from $H\_2 M \to ker(f\_\*) \subset H\_1 S\_g$. If you want this written explicity as an object in the kernel of $B$, recall that we are using the belt discs in the homology group $H\_1 S\_g$ as the last $g$ generators. To get these *belt disc coordinates*, again by Poincare duality we would compute the intersection number of the surface with the *core* curves of the first handlebody. 


