Algorithm  to check is representation irreducible ? Algorithm to decompose the reducible one ? Question 1 Given a representation of a finite group, what algorithm can be used to check is it irreducible or not ? 
(Main case - complex numbers, comments on other cases are also welcome. "Given" means finite set of matrices is given).
Question 2 Given a representation of a finite group, what algorithms can be used to decompose it to the direct sum of irreducibles) ? 

For the question 1 I would do the following: rep is irrep if its commutant consists of  scalar matrices. So I can try to find matrices commuting with  all elements of the group and look whether I get only scalar matrices.
Are there more effective ways to do it ?

Related question: How to compute all irreducible representations of a finite group ? (how GAP is doing this?)
 A: Some  years ago, we had to develop an approach inherited 
from Schützenberger's theory of automata (with weights) 
in order to explicitly split modules into indecomposable 
factors. 
The paper is available at 
http://lipn.univ-paris13.fr/~duchamp/Publications/decbf5.pdf
and was designed for cryptography (the general framework for 
modules is in section 3), but I developed the same 
concept in characteristic zero for modules of Hecke algebras.
The algorithm provides a certificate of indecomposability and 
I think it can give also a certificate of irreducibility.
I you are interested, I can explain.   
A: Here's a simple algorithm that was proposed in Dixon's 1970 paper: http://www.ams.org/journals/mcom/1970-24-111/S0025-5718-1970-0280611-6/S0025-5718-1970-0280611-6.pdf
It's split into 2 parts:
1. Construct a non-scalar commuting matrix $H$ (if possible)
Dixon presents two variants for part 1. I'll just mention the simpler one here. Let $\rho:G \to \text{GL}(n,\mathbb{C})$ be a (unitary) representation. For $r,s = 1,2,\dots,n$, define
$$
H_{rs} = \begin{cases}
E_{rr} &\text{if } r = s \\
E_{rs} + E_{sr} &\text{if } r > s \\
i(E_{rs} - E_{sr}) &\text{if } r < s,
\end{cases}
$$
where $E_{rs}$ is the $n \times n$ matrix with 1 in the $(r,s)^{th}$ entry and 0 everywhere else. Then $\{H_{rs}\}_{r,s=1}^n$ forms a Hermitian basis for the $n \times n$ matrices. 
Now for each $r,s$, compute the sum
$$
H = \frac{1}{|G|} \sum_{g \in G} \,\, \rho(g)^* \, H_{rs} \, \rho(g)
$$
Observe that $H$ commutes with all $\rho(g)$.
If $\rho$ is irreducible, then $H$ is a scalar matrix for all $r,s$. Otherwise, there will be some $r,s$ such that $H$ is non-scalar (because $\{H_{rs}\}_{r,s=1}^n$ forms a basis). In this case, proceed to part 2:
2. Use the eigenspaces of $H$ to decompose $\rho$
Let $H = UJU^*$ be the Jordan decomposition of $H$, where $U$ is unitary. Then
$$
U^* \rho(g) U
$$
will have the same block-diagonal form for all $g \in G$, yielding a decomposition of $\rho$.
Of course this assumes that the $n$ and $|G|$ are small enough that one can easily run through all the $H_{rs}$ and compute the Jordan decomposition. There are more sophisticated and efficient methods, but I like the simplicity of this one.
I've written an implementation of this algorithm in Sage.
A: I think this question is not quite so trivial as Qiaochu suggests. Devising practical algorithms for problems of this type is certainly an active area of research within the computational group theory community.
The first problem is that the group may be too large for it to be feasible to compute its conjugacy classes and character table. It might be one of the large sporadic simple groups for example. Over finite fields, the so-called Meataxe methods, which are actually just based on linear algebra, have been used to find the composition factors of some modules of dimensions in the hundreds of thousands. There are ongoing efforts to extend these methods to characteristic zero.
If your representation is in characteristic zero, and you can compute the classes and character table, then the straightforward character theoretic methods will tell you what the absolutely irreducible constituents of the module are, but that does not immediately enable you to decompose the module explicitly.
Another problem that arises in practice is that your representation may be over the rationals, for example, but its absolutely irreducible constituents might not be realizable over the rationals. In that case, the reducibility of the module will depend on the Schur Index of representation',s constituents, which can be calcualated from the character table. But again, if you find out, for example, that a rational representation is the direct sum of two isomorphic irreducibles, then it can be very difficult to find the basis change that exhibits the direct sum.
A: I don't know how to do this exactly, but one could try a probabilistic approach. Say the representation is $V$, and $V$ is defined over a $\mathbb{C}$ (or at least $\mathbb{Q}$). Pick a random non-zero element $v \in V$ and compute the dimension of the space spanned by the orbit $Gv$. If this dimension is $< \dim V$ then $V$ is reducible and (1) is answered. If not, try again. I would guess that if, after several iterations, the subrepresentations are all equal to $V$, then with high probability $V$ is multiplicity free (Edit. This did read "irreducible". As pointed out in the comments by Daniel Litt this is not so!).
The worst part about this algorithm (aside from not detecting reducibility) is having to list the elements of $G$.  But I guess this is already done according to Alexander's statement of the problem. You could also try to approximate the orbit. Say if $\dim V = 1000$ and $G = S_{12}$, then take some random $2000$ elements of $G$ and apply them $v$, and let this be your approximate orbit.
Another bad thing about this algorithm is that it can be numerically unstable.
