Fluids play a key role as a solvent in soft matter systems, even if they are not the primary target of investigation. Take, for example, biological cells propelling themselves by beating with flagella, i.e., slender appendages attached to the cell body. To move efficiently, it is often favorable to have nearby cells beat synchronously, which is achieved via hydrodynamic interactions: The beat of one cell's flagellum induces a flow field in the surrounding medium, which propagates and influences neighboring flagella [1, 2]. To study emergent phenomena like these via computer simulations, one can neither simply neglect the solvent (one would remove the interactions mediated by the fluid, and thus the phenomenon of interest), nor simulate every single molecule of the solvent and the solute: since the characteristic time- and length-scales of the macroscopic solutes are orders of magnitude larger than those of the microscopic solvent particles, both the number of simulated particles and the simulation time would need to become prohibitively large. So-called mesoscopic simulation techniques, such as Multiparticle Collision Dynamics (abbreviated MPC), aim to achieve a compromise by reducing the number of degrees of freedom while capturing the relevant physical properties. In MPC's original formulation [3, 4], the solvent is modeled by point particles, each representing a volume of the fluid that is large compared to the extent of a single fluid molecule, but small compared to the mesoscopic objects (solutes) in the system. The latter are modeled similarly, except that multiple MPC particles can be linked by arbitrary interaction potentials to form, e.g., the surface membrane of a biological cell. The two alternating simulation steps of MPC ("streaming" and "collision") are designed to yield hydrodynamic behavior by conserving mass and momentum, while retaining a high degree of computational parallelism, so that large systems can be simulated efficiently, especially on graphics processing units (GPUs). While this approach has been successfully employed in a variety of problems in fluid dynamics, one shortcoming of MPC, as introduced initially, is its inability to simulate non-Newtonian (viscoelastic) solvents, which occur frequently in both industrial and biological applications. To overcome this limitation, we consider a generalization of MPC by coupling N+1 MPC solvent particles via N harmonic springs to form a linear polymer [5-7]. We show that this simulated fluid exhibits non-Newtonian behavior; in particular, we study the autocorrelation of the Fourier-transformed fluid velocity field, which is found to decay exponentially, but with superimposed oscillations. We also derive a corresponding theoretical expression, and demonstrate excellent agreement on both qualitative and quantitative levels. Furthermore, we investigate the fluid behavior in the long-time limit, and find that it asymptotically tends to that of a purely viscous fluid [7]. [1] Lauga, E., Powers, T. R., Rep. Prog. Phys. 72, 096601 (2009) [2] Elgeti, J., Winkler, R. G., Gompper, G., Rep. Prog. Phys. 78, 056601 (2015) [3] Malevanets, A., Kapral, R., J. Chem. Phys. 110, 8605 (1999) [4] Gompper, G., Ihle, T. Kroll, D. M., Winkler, R. G., Adv. Polym. Sci. 221, 1 (2009) [5] Tao, Y.-G., Götze, I. O., Gompper, G., J. Chem. Phys 128, 144902 (2008) [6] Kowalik, B., Winkler, R. G., J. Chem. Phys. 138, 104903 (2013) [7] Toneian, D., Diploma Thesis, TU Wien (2015)