  We investigate the complexity of several fundamental polynomial-time solvable
problems on graphs and on matrices, when the given instance has low treewidth;
in the case of matrices, we consider the treewidth of the graph formed by
non-zero entries. In each of the considered cases, the best known algorithms
working on general graphs run in polynomial time, however the exponent of the
polynomial is large. Therefore, our main goal is to construct algorithms with
running time of the form $\textrm{poly}(k)\cdot n$ or $\textrm{poly}(k)\cdot
n\log n$, where $k$ is the width of the tree decomposition given on the input.
Such procedures would outperform the best known algorithms for the considered
problems already for moderate values of the treewidth, like $O(n^{1/c})$ for
some small constant $c$.
  Our results include:
  -- an algorithm for computing the determinant and the rank of an $n\times n$
matrix using $O(k^3\cdot n)$ time and arithmetic operations;
  -- an algorithm for solving a system of linear equations using $O(k^3\cdot
n)$ time and arithmetic operations;
  -- an $O(k^3\cdot n\log n)$-time randomized algorithm for finding the
cardinality of a maximum matching in a graph;
  -- an $O(k^4\cdot n\log^2 n)$-time randomized algorithm for constructing a
maximum matching in a graph;
  -- an $O(k^2\cdot n\log n)$-time algorithm for finding a maximum vertex flow
in a directed graph.
  Moreover, we give an approximation algorithm for treewidth with time
complexity suited to the running times as above. Namely, the algorithm, when
given a graph $G$ and integer $k$, runs in time $O(k^7\cdot n\log n)$ and
either correctly reports that the treewidth of $G$ is larger than $k$, or
constructs a tree decomposition of $G$ of width $O(k^2)$.
